Computing excluded minors

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Computing excluded minors

Full text

Pdf (389 KB)

Source

Symposium on Discrete Algorithms archive
Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms table of contents

San Francisco, California

Pages 641-650

Year of Publication: 2008

Authors

Isolde Adler	Institut für Informatik, Humboldt Universität zu Berlin
Martin Grohe	Institut für Informatik, Humboldt Universität zu Berlin
Stephan Kreutzer	Oxford University

Sponsors

: SIAM Activity Group on Discrete Mathematics
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Society for Industrial and Applied Mathematics Philadelphia, PA, USA

Bibliometrics

Downloads (6 Weeks): 7, Downloads (12 Months): 46, Citation Count: 1

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

ABSTRACT

By Robertson and Seymour's graph minor theorem, every minor ideal can be characterised by a finite family of excluded minors. (A minor ideal is a class of graphs closed under taking minors.) We study algorithms for computing excluded minor characterisations of minor ideals. We propose a general method for obtaining such algorithms, which is based on definability in monadic second-order logic and the decidability of the monadic second-order theory of trees. A straightforward application of our method yields algorithms that, for a given k, compute excluded minor characterisations for the minor ideal T_k of all graphs of tree width at most k, the minor ideal B_k of all graphs of branch width at most k, and the minor ideal G_k of all graphs of genus at most k.

Our main results are concerned with constructions of new minor ideals from given ones. Answering a question that goes back to Fellows and Langston [11], we prove that there is an algorithm that, given excluded minor characterisations of two minor ideals C and D, computes such a characterisation for the ideal C ∪ D. Furthermore, we obtain an algorithm for computing an excluded minor characterisation for the class of all apex graphs over a minor ideal C, given an excluded minor characterisation for C. (An apex graph over C is a graph G from which one vertex can be removed to obtain a graph in C.) A corollary of this result is a uniform ftpalgorithm for the "distance k from planarity" problem.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Hans L. Bodlaender , Ton Kloks, Efficient and constructive algorithms for the pathwidth and treewidth of graphs, Journal of Algorithms, v.21 n.2, p.358-402, Sept. 1996 [doi>10.1006/jagm.1996.0049]
	2	Hans L. Bodlaender , Dimitrios M. Thilikos, Constructive Linear Time Algorithms for Branchwidth, Proceedings of the 24th International Colloquium on Automata, Languages and Programming, p.627-637, July 07-11, 1997
	3	Kevin Cattell , Michael J. Dinneen , Rodney G. Downey , Michael R. Fellows , Michael A. Langston, On computing graph minor obstruction sets, Theoretical Computer Science, v.233 n.1-2, p.107-127, Feb. 28 2000 [doi>10.1016/S0304-3975(97)00300-9]
	4	Brouno Courcelle, Graph rewriting: an algebraic and logic approach, Handbook of theoretical computer science (vol. B): formal models and semantics, MIT Press, Cambridge, MA, 1991
	5	B. Courcelle, R. G. Downey, and M. R. Fellows. A note on the computability of graph minor obstruction sets for monadic second order ideals. Journal of Universal Computer Science, 3:1194--1198, 1997.
	6	R. G. Downey and M. R. Fellows. Parameterized Complexity. Springer-Verlag, 1999.
	7	H.-D. Ebbinghaus and J. Flum. Finite Model Theory. Springer, 2nd edition, 1999.
	8	D. Eppstein. Diameter and treewidth in minor-closed graph families. Algorithmica, 27:275--291, 2000.
	9	M. R. Fellows , M. A. Langston, Nonconstructive advances in polynomial-time complexity, Information Processing Letters, v.26 n.3, p.155-162, Nov. 23, 1987
	10	Michael R. Fellows , Michael A. Langston, Nonconstructive tools for proving polynomial-time decidability, Journal of the ACM (JACM), v.35 n.3, p.727-739, July 1988 [doi>10.1145/44483.44491]
	11	M. R. Fellows and M. A. Langston. An analogue of the Myhill-Nerode theorem and its use in computing finite basis characterizations. In Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science, pages 520--525, 1989.
	12	M. R. Fellows , M. A. Langston, On search decision and the efficiency of polynomial-time algorithms, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.501-512, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73055]
	13	J. F. Geelen , A. M. H. Gerards , N. Robertson , G. P. Whittle, On the excluded minors for the matroids of branch-width k, Journal of Combinatorial Theory Series B, v.88 n.2, p.261-265, July 2003 [doi>10.1016/S0095-8956(02)00046-1]
	14	Martin Grohe, Local Tree-Width, Excluded Minors, and Approximation Algorithms, Combinatorica, v.23 n.4, p.613-632, December 2003 [doi>10.1007/s00493-003-0037-9]
	15	M. Dinneen K. Cattell and M. Fellows. Forbidden minors to graphs with small feedback sets. Discrete Mathematics, 230:215--252, 2001.
	16	Jens Lagergren, Upper bounds on the size of obstructions and intertwines, Journal of Combinatorial Theory Series B, v.73 n.1, p.7-40, May 1, 1998 [doi>10.1006/jctb.1997.1788]
	17	D. Marx and I. Schlotter. Obtaining a planar graph by vertex deletion. In Proceedings of the 33rd Workshop on Graph-Theoretic Concepts in Computer Science, 2007.
	18	B. Mohar and C. Thomassen. Graphs on Surfaces. Johns Hopkins University Press, 2001.
	19	N. Robertson and P. D. Seymour. Graph minors XXII. Irrelevant vertices in linkage problems. To appear.
	20	Neil Robertson , P. D. Seymour, Graph minors: X. obstructions to tree-decomposition, Journal of Combinatorial Theory Series B, v.52 n.2, p.153-190, July 1991 [doi>10.1016/0095-8956(91)90061-N]
	21	Neil Robertson , P. D. Seymour, Graph minors. XIII: the disjoint paths problem, Journal of Combinatorial Theory Series B, v.63 n.1, p.65-110, Jan. 1995 [doi>10.1006/jctb.1995.1006]
	22	Neil Robertson , P. D. Seymour, Graph Minors. XX. Wagner's conjecture, Journal of Combinatorial Theory Series B, v.92 n.2, p.325-357, November 2004 [doi>10.1016/j.jctb.2004.08.001]
	23	D. Seese. The structure of models of decidable monadic theories of graphs. Annals of Pure and Applied Logic, 53:169--195, 1991.
	24	P. Seymour. A bound on the excluded minors for a surface, 1995. Unpublished manuscript.
	25	Carsten Thomassen, A simpler proof of the excluded minor theorem for higher surfaces, Journal of Combinatorial Theory Series B, v.70 n.2, p.306-311, July 1997 [doi>10.1006/jctb.1997.1761]