Abstract
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. It has been shown that this problem is NP-hard even for chordal graphs [17], and there is probably no PTAS for general graphs [12]. However, the exact complexity status for interval graphs is a long-standing open problem [17], and the best known approximation result is a 3-approximation algorithm [16]. 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+ε)-approximation algorithm for any ε > 0, which is the first such approximation scheme for the densest k-subgraph problem in an important graph class without any further restrictions.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Arora, S.: Polynomial time approximation schemes for euclidean traveling salesman and other geometric problems. Journal of the ACM 45(5), 753–782 (1998)
Arora, S., Karger, D.R., Karpinski, M.: Polynomial time approximation schemes for dense instances of np-hard problems. J. Comput. Syst. Sci. 58(1), 193–210 (1999)
Asahiro, Y., Iwama, K., Tamaki, H., Tokuyama, T.: Greedily finding a dense subgraph. J. Algorithms 34(2), 203–221 (2000)
Backer, J., Keil, J.M.: 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)
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 2010), pp. 201–210 (2010)
Chen, D.Z., Fleischer, R., Li, J.: Densest k-subgraph approximation on intersection graphs. In: Jansen, K., Solis-Oba, R. (eds.) WAOA 2010. LNCS, vol. 6534, pp. 83–93. Springer, Heidelberg (2011)
Feige, U., Langberg, M.: Approximation algorithms for maximization problems arising in graph partitioning. J. Algorithms 41(2), 174–211 (2001)
Feige, U., Peleg, D., Kortsarz, G.: The dense k-subgraph problem. Algorithmica 29(3), 410–421 (2001)
Golumbic, M.C., Trenk, A.N.: Tolerance Graphs. Cambridge University Press, Cambridge (2004)
Gröschel, M., Lovász, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Springer, Heidelberg (1988)
Ibarra, O.H., Kim, C.E.: Fast approximation algorithms for the knapsack and sum of subset problems. Journal of the ACM 22 (1975)
Khot, S.: Ruling out ptas for graph min-bisection, dense k-subgraph, and bipartite clique. SIAM J. Comput. 36(4), 1025–1071 (2006)
Kortsarz, G., Peleg, D.: On choosing a dense subgraph. In: Proceedings of the 34th Annual Symposium on Foundations of Computer Science (FOCS 1993), pp. 692–701 (1993)
Lawler, E.L.: Combinatorial optimization - networks and matroids. Holt, Rinehart and Winston, New York (1976)
Liazi, M., Milis, I., Pascual, F., Zissimopoulos, V.: The densest k-subgraph problem on clique graphs. J. Comb. Optim. 14(4), 465–474 (2007)
Liazi, M., Milis, I., Zissimopoulos, V.: A constant approximation algorithm for the densest k-subgraph problem on chordal graphs. Inf. Process. Lett. 108(1), 29–32 (2008)
Perl, Y., Corneil, D.G.: Clustering and domination in perfect graphs. Discrete Applied Mathematics 9(1), 27–39 (1984)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Nonner, T. (2011). PTAS for Densest k-Subgraph in Interval Graphs. In: Dehne, F., Iacono, J., Sack, JR. (eds) Algorithms and Data Structures. WADS 2011. Lecture Notes in Computer Science, vol 6844. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-22300-6_53
Download citation
DOI: https://doi.org/10.1007/978-3-642-22300-6_53
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-22299-3
Online ISBN: 978-3-642-22300-6
eBook Packages: Computer ScienceComputer Science (R0)