Quantcast

Finding connected k-subgraphs with high density☆☆☆

Research paper by XujinChena, XiaodongHua, ChangjunWangb

Indexed on: 10 Nov '17Published on: 01 Oct '17Published in: Information and Computation



Abstract

Given an edge-weighted connected graph G on n vertices and a positive integer k≤n<math class="math"><mi is="true">k</mi><mo is="true">≤</mo><mi is="true">n</mi></math>, a subgraph of G on k vertices is called a k-subgraph in G. We design combinatorial approximation algorithms for finding a connected k-subgraph in G such that its weighted density is at least a factor Ω(max⁡{1/k,k2/n2})<math class="math"><mi mathvariant="normal" is="true">Ω</mi><mo stretchy="false" is="true">(</mo><mi mathvariant="normal" is="true">max</mi><mo is="true">⁡</mo><mo stretchy="false" is="true">{</mo><mn is="true">1</mn><mo stretchy="false" is="true">/</mo><mi is="true">k</mi><mo is="true">,</mo><msup is="true"><mrow is="true"><mi is="true">k</mi></mrow><mrow is="true"><mn is="true">2</mn></mrow></msup><mo stretchy="false" is="true">/</mo><msup is="true"><mrow is="true"><mi is="true">n</mi></mrow><mrow is="true"><mn is="true">2</mn></mrow></msup><mo stretchy="false" is="true">}</mo><mo stretchy="false" is="true">)</mo></math> of the maximum weighted density among all k-subgraph in G (which are not necessarily connected), where max⁡{1/k,k2/n2}≥n−2/3<math class="math"><mi mathvariant="normal" is="true">max</mi><mo is="true">⁡</mo><mo stretchy="false" is="true">{</mo><mn is="true">1</mn><mo stretchy="false" is="true">/</mo><mi is="true">k</mi><mo is="true">,</mo><msup is="true"><mrow is="true"><mi is="true">k</mi></mrow><mrow is="true"><mn is="true">2</mn></mrow></msup><mo stretchy="false" is="true">/</mo><msup is="true"><mrow is="true"><mi is="true">n</mi></mrow><mrow is="true"><mn is="true">2</mn></mrow></msup><mo stretchy="false" is="true">}</mo><mo is="true">≥</mo><msup is="true"><mrow is="true"><mi is="true">n</mi></mrow><mrow is="true"><mo is="true">−</mo><mn is="true">2</mn><mo stretchy="false" is="true">/</mo><mn is="true">3</mn></mrow></msup></math> implies an O(n2/3)<math class="math"><mi is="true">O</mi><mo stretchy="false" is="true">(</mo><msup is="true"><mrow is="true"><mi is="true">n</mi></mrow><mrow is="true"><mn is="true">2</mn><mo stretchy="false" is="true">/</mo><mn is="true">3</mn></mrow></msup><mo stretchy="false" is="true">)</mo></math>-approximation ratio. We obtain improved O(n2/5)<math class="math"><mi is="true">O</mi><mo stretchy="false" is="true">(</mo><msup is="true"><mrow is="true"><mi is="true">n</mi></mrow><mrow is="true"><mn is="true">2</mn><mo stretchy="false" is="true">/</mo><mn is="true">5</mn></mrow></msup><mo stretchy="false" is="true">)</mo></math>-approximation for unit weights. These particularly provide the first non-trivial approximations for the heaviest/densest connected k-subgraph problem on general graphs. We also give O(nlog⁡n)<math class="math"><mi is="true">O</mi><mo stretchy="false" is="true">(</mo><msqrt is="true"><mi is="true">n</mi></msqrt><mi mathvariant="normal" is="true">log</mi><mo is="true">⁡</mo><mi is="true">n</mi><mo stretchy="false" is="true">)</mo></math>-approximation for the problem on general weighted interval graphs.