Abstract
Our goal in this paper is the development of fast algorithms for recognizing general classes of graphs. We seek algorithms whose complexity can be expressed as a linear function of the graph size plus an exponential function of k, a natural parameter describing the class. Our classes are of the form \( \mathcal{W}_k (\mathcal{G}) \), graphs that can be formed by augmenting graphs in \( \mathcal{G} \) by adding at most k vertices (and incident edges). If \( \mathcal{G} \) is the class of edgeless graphs, \( \mathcal{W}_k (\mathcal{G}) \) is the class of graphs with a vertex cover of size at most k.
We describe a recognition algorithm for \( \mathcal{W}_k (\mathcal{G}) \) running in time O((g + k)|V(G)| + (fk) k), where g and f are modest constants depending on the class \( \mathcal{G} \), when \( \mathcal{G} \) is a minor-closed class such that each graph in G has bounded maximum degree, and all obstructions of G (minor-minimal graphs outside \( \mathcal{G} \)) are connected. If \( \mathcal{G} \) is the class of graphs with maximum degree bounded by D (not closed under minors), we can still recognize graphs in \( \mathcal{W}_k (\mathcal{G}) \) in time O(|V(G)|(D + k) + k(D + k) k+3).
Our results are obtained by considering minor-closed classes \( \mathcal{G} \) for which all obstructions are connected graphs, and showing that the size of any obstruction for \( \mathcal{W}_k (\mathcal{G}) \) is O(tk 7 + t 7 k 2), where t is a bound on the size of obstructions for \( \mathcal{G} \).
Research supported by the Natural Sciences and Engineering Research Council of Canada, Ministry of Education and Culture of Spain (grant number MEC-DGES SB98 0K148809), and EU project ALCOM-FT (IST-99-14186).
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Stefan Arnborg. Efficient algorithms for combinatorial problems on graphs with bounded decomposability-A survey. BIT, 25:2–23, 1985.
R. Balasubramanian, Michael Fellows, and Venkatesh Raman. An improved fixed-parameter algorithm for vertex cover. Inform. Proc. Letters, 65:163–168, 1998.
Jonathan F. Buss and Judy Goldsmith. Nondeterminism within P. SIAM J. Computing, 22:560–572, 1993.
Daniel Bienstock, Neil Robertson, Paul D. Seymour, and Robin Thomas. Quickly excluding a forest. J. Comb. Theory Series B, 52:274–283, 1991.
Leizhen Cai. Fixed-parameter tractability of graph modification problems for hereditary properties. Inform. Proc. Letters, 58:171–176, 1996.
Liming Cai, Jianer Chen, Rodney Downey, and Michael Fellows. Advice classes of parameterized tractability. Annals of Pure and Applied Logic, 84:119–138, 1997.
J. Chen, I.A. Kanj, and W. Jia. Vertex cover: Further observations and further improvements. In Proceedings of the 25th International Workshop on Graph-Theoretical Concepts in Computer Science, pages 313–324. Springer-Verlag, 1999.
Rodney G. Downey and Michael R. Fellows. Fixed-parameter tractability and completeness I: Basic results. SIAM J. Comput., 24:873–921, 1995.
Rodney G. Downey and Michael R. Fellows. Parameterized Complexity. Springer-Verlag, 1999.
Rodney G. Downey, Michael R. Fellows, and Ulrike Stege. Computational tractability: the view from Mars. Bulletin of the European Association of Theoretical Computer Science, 69:73–97, 1999.
Michael J. Dinneen. Bounded Combinatorial Width and Forbidden Substructures. PhD thesis, Department of Computer Science, University of Victoria, 1995.
Michael J. Dinneen. Too many minor order obstructions (for parametrized lower ideals). Journal of Universal Computer Science, 3(11):1199–1206, 1997.
Michael R. Fellows and Michael A. Langston. Nonconstructive tools for proving polynomial-time decidability. J. ACM, 35:727–739, 1988.
Michael R. Fellows and Michael A. Langston. On search, decision, and the efficiency of polynomial-time algorithms. J. Comp. Syst. Sc., 49(3):769–779, 1994.
Martin Farach, Teresa Przytycka, and Mikkel Thorup. On the agreement of many trees. Inform. Proc. Letters, 55:297–301, 1995.
Harvey Friedman, Neil Robertson, and Paul D. Seymour. The metamathe-matics of the graph minor theorem. Contemporary Mathematics, 65:229–261, 1987.
Haim Kaplan, Ron Shamir, and Robert E. Tarjan. Tractability of parameterized completion problems on chordal, strongly chordal, and proper interval graphs. SIAM J. Comput., 28(5):1906–1922, 1999.
Jens Lagergren. An upper bound on the size of an obstruction. In Neil Robertson and Paul Seymour, editors, Graph Structure Theory, Proceedings of the AMS-IMS-SIAM Joint Summer Research Conference, Seattle WA, June 1991, pages 601–621, Providence, RI, 1993. American Math. Soc. Contemp. Math. 147.
Jens Lagergren. Upper bounds on the size of obstructions and intertwines. J. Combin. Theory Ser. B, 73:7–40, 1998.
J. M. Lewis and Christos H. Papadimitriou. The node-deletion problem for hereditary properties is NP-complete. J. Comp. Syst. Sc., 20:219–230, 1980.
Michael A Langston and Barbara C. Plaut. On algorithmic applications of the immersion order. An overview of ongoing work presented at the Third Slovenian International Conference on Graph Theory. Discrete Mathematics, 182(1–3):191–196, 1998.
Kurt Mehlhorn. Graph Algorithms and NP-Completeness, volume 2 of Data Structures and Algorithms. Springer Verlag, Berlin, 1984.
Meena Mahajan and Venkatesh Raman. Parameterizing above guaranteed values: maxsat and maxcut. J. Algorithms, 31(2):335–354, May 1999.
Rolf Niedermeier. Some prospects for efficient fixed parameter algorithms. In Proceedings of the 25th Conference on Current Trends in Theory and Practice of Informatics (SOFSEM’98), volume 1521 of Lecture Notes in Computer Science, pages 168–185, 1998.
Rolf Niedermeier and Peter Rossmanith. Upper bounds for vertex cover further improved. In C. Meinel, S. Tison, editors, Proceedings of the 16th Symposium on Theoretical Aspects of Computer Science (STACS’99), volume 1563 of Lecture Notes in Computer Science, pages 561–570, 1999.
Siddharthan Ramachandramurthi. A lower bound for treewidth and its consequences. In Ernst W. Mayr, Gunther Schmidt, and Gottfried Tinhofer, editors, Proceedings 20th International Workshop on Graph Theoretic Concepts in Computer Science WG’94, volume 903 of Lecture Notes in Computer Science, pages 14–25. Springer Verlag, 1995.
Neil Robertson and Paul D. Seymour. Disjoint paths-A survey. SIAM J. Alg. Disc. Meth., 6:300–305, 1985.
Neil Robertson and Paul D. Seymour. Graph minors — A survey. In I. Anderson, editor, Surveys in Combinatorics, pages 153–171. Cambridge Univ. Press, 1985.
Neil Robertson and Paul D. Seymour. Graph minors. XIII. The disjoint paths problem. J. Comb. Theory Series B, 63:65–110, 1995.
Dimitrios M. Thilikos. Algorithms and obstructions for linear-width and related search parameters. Discrete Applied Mathematics, 105:239–271, 2000.
Atsushi Takahashi, Shuichi Ueno, and Yoji Kajitani. Minimal acyclic forbidden minors for the family of graphs with bounded path-width. Discrete Mathematics, 127(1/3):293–304, 1994.
Jan van Leeuwen. Graph algorithms. In Handbook of Theoretical Computer Science, A: Algorithms and Complexity Theory, pages 527–631, Amsterdam, 1990. North Holland Publ. Comp.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Nishimura, N., Ragde, P., Thilikos, D.M. (2001). Fast Fixed-Parameter Tractable Algorithms for Nontrivial Generalizations of Vertex Cover. In: Dehne, F., Sack, JR., Tamassia, R. (eds) Algorithms and Data Structures. WADS 2001. Lecture Notes in Computer Science, vol 2125. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44634-6_8
Download citation
DOI: https://doi.org/10.1007/3-540-44634-6_8
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42423-9
Online ISBN: 978-3-540-44634-7
eBook Packages: Springer Book Archive