Abstract
We study three complexity parameters that in some sense measure how chordal-like a graph is. The similarity to chordal graphs is used to construct simple polynomial-time approximation algorithms with constant approximation ratio for many \(\mathcal{NP}\)-hard problems, when restricted to graphs for which at least one of the three complexity parameters is bounded by a constant. As applications we present approximation algorithms with constant approximation ratio for maximum weighted independent set, minimum (independent) dominating set, minimum vertex coloring, maximum weighted clique, and minimum clique partition for large classes of intersection graphs.
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
Akcoglu, K., Aspnes, J., DasGupta, B., Kao, M.-Y.: Opportunity cost algorithms for combinatorial auctions. In: Kontoghiorghes, E.J., Rustem, B., Siokos, S. (eds.) Applied Optimization: Computational Methods in Decision Making, Economics and Finance, vol. 74, pp. 455–479 (2002)
Bar-Yehuda, R., Halldórsson, M.M., Naor, J., Shachnai, H., Shapira, I.: Scheduling split intervals. SIAM J. Comput. 36, 1–15 (2006)
Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25, 1305–1317 (1996)
Butman, A., Hermelin, D., Lewenstein, M., Rawitz, D.: Optimization problems in multiple-interval graphs. In: Proc.18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2007), pp. 268–277 (2007)
Cerioli, M.R., Faria, L., Ferreira, T.O., Protti, F.: On minimum clique partition and maximum independent set on unit disk graphs and penny graphs: complexity and approximation. Electronic Notes in Discrete Mathematics 18, 73–79 (2004)
Chan, T.M.: Polynomial-time approximation schemes for packing and piercing fat objects. J. Algorithms 46, 178–189 (2003)
Clark, B.N., Colbourn, C.J., Johnson, D.S.: Unit disk graphs. Discrete Math. 86, 165–177 (1990)
Courcelle, B.: The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inform. and Comput. 85, 12–75 (1990)
Dumitrescu, A., Pach, J.: Minimum clique partition in unit disk graphs, arXiv:0909.1552v1
Erlebach, T., Jansen, K., Seidel, E.: Polynomial-time approximation schemes for geometric intersection graphs. In: Proc. 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2001), pp. 671–679 (2001)
Erlebach, T., van Leeuwen, E.J.: Domination in geometric intersection graphs. In: Laber, E.S., Bornstein, C., Nogueira, L.T., Faria, L. (eds.) LATIN 2008. LNCS, vol. 4957, pp. 747–758. Springer, Heidelberg (2008)
Fowler, R.J., Paterson, M.S., Tanimoto, S.L.: Optimal packing and covering in the plane are NP-complete. Inform. Process. Lett. 12, 133–137 (1981)
Frank, A.: Some polynomial algorithms for certain graphs and hypergraphs. In: Proc. 5th British Combinatorial Conference (Aberdeen 1975), Congr. Numer. XV., pp. 211–226 (1976)
Garey, M.R., Johnson, D.S., Stockmeyer, L.: Some simplified NP-complete graph problems. Theoret. Comput. Sci. 1, 237–267 (1976)
Gavril, F.: Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph. SIAM J. Comput. 1, 180–187 (1972)
Gibson, T., Pirwani, I.A.: Approximation algorithms for dominating set in disk graphs. In: Proc. 18th Annual European Symposium on Algorithms (ESA 2010). LNCS. Springer, Heidelberg (2010) (to appear)
Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York (1980)
Golumbic, M.C.: Algorithmic aspects of intersection graphs and representation hypergraphs. Graphs and Combinatorics 4, 307–321 (1988)
Gräf, A.: Coloring and recognizing special graph classes, Technical Report Musikinformatik und Medientechnik Bericht 20/95, Johannes Gutenberg-Universität Mainz (1995)
Gramm, J., Guo, J., Hüffner, F., Niedermeier, R.: Data reduction and exact algorithms for clique cover. Journal of Experimental Algorithmics 13, Article No. 2 (2009)
Griggs, J.R., West, D.B.: Extremal values of the interval number of a graph. SIAM Journal on algebraic and discrete methods 1, 1–7 (1980)
Hunt III, H.B., Marathe, M.V., Radhakrishnan, V., Ravi, S.S., Rosenkrantz, D.J., Stearns, R.E.: NC-pproximation schemes for NP- and PSPACE-hard problems for geometric graphs. J. Algorithms 26, 238–274 (1998)
Hurink, J.L., Nieberg, T.: Approximating minimum independent dominating sets in wireless networks. Inform. Process. Lett. 109, 155–160 (2008)
Imai, H., Asano, T.: Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane. J. Algorithms 4, 310–323 (1983)
Jamison, R.E., Mulder, H.M.: Tolerance intersection graphs on binary trees trees with constant tolerance 3. Discrete Math. 215, 115–131 (2000)
Johnson, D.S.: Approximation algorithms for combinatorial problems. J. Comput. System Sci. 9, 256–278 (1974)
Kammer, F., Tholey, T., Voepel, H.: Approximation algorithms for intersection graphs, Report 2009–6, Institut für Informatik, Universität Augsburg (2009)
Malesińska, E.: Graph-theoretical models for frequency assignment problems, PhD thesis, University of Berlin (1997)
Marathe, M.V., Breu, H., Hunt III, H.B., Ravi, S.S., Rosenkrantz, D.J.: Simple heuristics for unit disk graphs. Networks 25, 59–68 (1995)
Nieberg, T., Hurink, J., Kern, W.: Approximation Schemes for Wireless Networks. ACM Transactions on Algorithms 4, Article No. 49 (2008)
Papadimitriou, C.H., Yannakakis, M.: Optimization, approximation, and complexity classes. J. Comput. System Sci. 43, 425–440 (1991)
Pirwani, I.A., Salavatipour, M.R.: A weakly-robust PTAS for minimum clique partition on unit disk graphs. In: Kaplan, H. (ed.) SWAT 2010. LNCS, vol. 6139, pp. 188–199. Springer, Heidelberg (2010)
Tardos, É.: A strongly polynomial algorithm to solve combinatorial linear programs. Operations Research 34, 250–256 (1986)
Ye, Y., Borodin, A.: Elimination graphs. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009. LNCS, vol. 5556, pp. 774–785. Springer, Heidelberg (2009)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kammer, F., Tholey, T., Voepel, H. (2010). Approximation Algorithms for Intersection Graphs. In: Serna, M., Shaltiel, R., Jansen, K., Rolim, J. (eds) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. RANDOM APPROX 2010 2010. Lecture Notes in Computer Science, vol 6302. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-15369-3_20
Download citation
DOI: https://doi.org/10.1007/978-3-642-15369-3_20
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-15368-6
Online ISBN: 978-3-642-15369-3
eBook Packages: Computer ScienceComputer Science (R0)