PTAS for Densest \(k\) -Subgraph in Interval Graphs

详细信息    查看全文

• 作者：Tim Nonner
• 关键词：Algorithms ; Approximation algorithms ; Graph algorithms ; Approximation schemes ; Interval graphs
• 刊名：Algorithmica
• 出版年：2016
• 出版时间：January 2016
• 年：2016
• 卷：74
• 期：1
• 页码：528-539
• 全文大小：529 KB
• 参考文献：1.Perl, Y., Corneil, D.G.: Clustering and domination in perfect graphs. Discret. Appl. Math. 9(1), 27–39 (1984)MATH MathSciNet CrossRef
  2.Khot, Subhash: Ruling out ptas for graph min-bisection, dense k-subgraph, and bipartite clique. SIAM J. Comput. 36(4), 1025–1071 (2006)MATH MathSciNet CrossRef
  3.Liazi, Maria, Milis, Ioannis, Zissimopoulos, Vassilis: A constant approximation algorithm for the densest k-subgraph problem on chordal graphs. Inf. Process. Lett. 108(1), 29–32 (2008)MATH MathSciNet CrossRef
  4.Lawler, Eugene L.: Combinatorial Optimization—Networks and Matroids. Holt, Rinehart and Winston, New York (1976)MATH
  5.Kortsarz, G., Peleg, D.: On choosing a dense subgraph. In Proceedings of the 34th Annual Symposium on Foundations of Computer Science (FOCS’93), pp. 692–701 (1993)
  6.Feige, Uriel, Peleg, David, Kortsarz, Guy: The dense k-subgraph problem. Algorithmica 29(3), 410–421 (2001)MATH MathSciNet CrossRef
  7.Bhaskara, A., Charikar, M., Chlamtac, E., Feige, U., Vijayaraghavan, A.: Detecting high log-densities: an \( {O}(n^{1/4}) \) -approximation for densest k-subgraph. In Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC’10), pp. 201–210 (2010)
  8.Asahiro, Yuichi, Iwama, Kazuo, Tamaki, Hisao, Tokuyama, Takeshi: Greedily finding a dense subgraph. J. Algorithms 34(2), 203–221 (2000)MATH MathSciNet CrossRef
  9.Feige, Uriel, Langberg, Michael: Approximation algorithms for maximization problems arising in graph partitioning. J. Algorithms 41(2), 174–211 (2001)MATH MathSciNet CrossRef
  10.Arora, Sanjeev, Karger, David R., Karpinski, Marek: Polynomial time approximation schemes for dense instances of np-hard problems. J. Comput. Syst. Sci. 58(1), 193–210 (1999)MATH MathSciNet CrossRef
  11.Gröschel, M., Lovász, László, Schrijver, Alexander: Geometric Algorithms and Combinatorial Optimizatio. Springer, New York (1988)CrossRef
  12.Golumbic, Martin Charles, Trenk, Ann N.: Tolerance Graphs. Cambridge University Press, Cambridge (2004)MATH CrossRef
  13.Liazi, Maria, Milis, Ioannis, Pascual, Fanny, Zissimopoulos, Vassilis: The densest k-subgraph problem on clique graphs. J. Comb. Optim. 14(4), 465–474 (2007)MATH MathSciNet CrossRef
  14.Chen, D.Z., Fleischer, R., Li, J.: Densest k-subgraph approximation on intersection graphs. In Proceedings of the 8th International Workshop on Approximation and Online Algorithms (WAOA’10), pp. 83–93 (2010)
  15.Backer, Jonathan, Mark Keil, J.: Constant factor approximation algorithms for the densest k-subgraph problem on proper interval graphs and bipartite permutation graphs. Inf. Process. Lett. 110(16), 635–638 (2010)MATH CrossRef
  16.Arora, Sanjeev: Polynomial time approximation schemes for euclidean traveling salesman and other geometric problems. J. ACM 45(5), 753–782 (1998)MATH MathSciNet CrossRef
  17.Ibarra, O.H., Kim, C.E.: Fast approximation algorithms for the knapsack and sum of subset problems. J. ACM 22, 463–468 (1975)
  18.Watrigant, R., Bougeret, M., Giroudeau, R.: Approximating the sparsest k-subgraph in chordal graphs. In Proceedings of the 11th Workshop on Approximation and Online Algorithms (WAOA’13) (2013)
  
• 作者单位：Tim Nonner (1)
  
  1. IBM Research, Zurich, Switzerland
  
• 刊物类别：Computer Science
• 刊物主题：Algorithm Analysis and Problem Complexity
  Theory of Computation
  Mathematics of Computing
  Algorithms
  Computer Systems Organization and Communication Networks
  Data Structures, Cryptology and Information Theory
  
• 出版者：Springer New York
• ISSN：1432-0541

文摘

Given an interval graph and integer \(k\), we consider the problem of finding a subgraph of size \(k\) with a maximum number of induced edges, called densest k -subgraph problem in interval graphs. This problem is NP-hard even for chordal graphs (Perl and Corneil in Discret Appl Math 9(1):27–39, 1984), and there is probably no PTAS for general graphs (Khot and Subhash in SIAM J Comput 36(4):1025–1071, 2006). However, the exact complexity status for interval graphs is a long-standing open problem (Perl and Corneil in Discret Appl Math 9(1):27–39, 1984), and the best known approximation result is a \( 3 \)-approximation algorithm (Liazi et al. in Inf Process Lett 108(1):29–32, 2008). We shed light on the approximation complexity of finding a densest \( k \)-subgraph in interval graphs by presenting a polynomial-time approximation scheme (PTAS), that is, we show that there is an \( (1+\epsilon ) \)-approximation algorithm for any \( \epsilon > 0 \), which is the first such approximation scheme for the densest \( k \)-subgraph problem in an important graph class without any further restrictions.