Faster parameterized algorithms for minor containment

Abstract: The -Minor containment problem asks whether a graph contains some fixed graph as a minor, that is, whether can be obtained by some subgraph of after contracting edges. The derivation of a polynomial-time algorithm for -Minor containment is one of the most important and technical parts of the Graph Minor Theory of Robertson and Seymour and it is a cornerstone for most of the algorithmic applications of this theory. -Minor containment for graphs of bounded branchwidth is a basic ingredient of this algorithm. The currently fastest solution to this problem, based on the ideas introduced by Robertson and Seymour, was given by Hicks in [I.V. Hicks, Branch decompositions and minor containment, Networks 43 (1) (2004) 1–9], providing an algorithm that in time decides if a graph with edges and branchwidth , contains a fixed graph on vertices as a minor. In this work we improve the dependence on of Hicks’ result by showing that checking if is a minor of can be done in time . We set up an approach based on a combinatorial object called rooted packing, which captures the properties of the subgraphs of that we seek in our dynamic programming algorithm. This formulation with rooted packings allows us to speed up the algorithm when is embedded in a fixed surface, obtaining the first algorithm for minor containment testing with single-exponential dependence on branchwidth. Namely, it runs in time , with . Finally, we show that slight modifications of our algorithm permit to solve some related problems within the same time bounds, like induced minor or contraction containment. [Copyright &y& Elsevier]