On Linear Time Minor Tests with Depth-First Search

Recent results on graph minors make it desirable to have efficient algorithms that, for a fixed set of graphs {H₁,...,H_c}, 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 × k grid graph, and at least one graph H_i is a minor of a circus graph, then one can test in O(n) time whether a given graph G contains at least one graph H ∈ {H₁,..., H_c} 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 O(k! 2^kn) time a cycle (or path) in a given graph with length ≥ k if it exists.