On Linear Time Minor Tests with Depth-First Search

✍ Scribed by H.L. Bodlaender

• Publisher: Elsevier Science
• Year: 1993
• Tongue: English
• Weight: 911 KB
• Volume: 14
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.1993.1001

✦ Synopsis

Recent results on graph minors make it desirable to have efficient algorithms that, for a fixed set of graphs (\left{H_{1}, \ldots, H_{c}\right}), test whether a given graph (G) contains at least one graph (H_{i}) as a minor. In this paper we show the following result: if at least one graph (H_{i}) is a minor of a (2 \times k) grid graph, and at least one graph (H_{i}) is a minor of a circus graph, then one can test in (\mathscr{O}(n)) time whether a given graph (G) contains at least one graph (H \in\left{H_{1}, \ldots, H_{\mathrm{c}}\right}) as a minor. This result generalizes a result of Fellows and Langston. The algorithm is based on depth-first search and on dynamic programming on graphs with bounded treewidth. As a corollary, it follows that the MAXIMUM LEAF SPANNING TREE problem can be solved in linear time for fixed (k). We also discuss that, with small modifications, an algorithm of Fellows and Langston can be modified to an algorithm that finds in (\mathcal{O}\left(k!2^{k} n\right)) time a cycle (or path) in a given graph with length (\geq k) if it exists. 1993 Academic Press, Inc.