Faster parameterized algorithms for minor containment

Isolde Adler, Frederic Dorn, Fedor V. Fomin, Ignasi Sau, Dimitrios M. Thilikos

Research output: Contribution to journalArticlepeer-review


The H-Minor containment problem asks whether a graph G contains some fixed graph H as a minor, that is, whether H can be obtained by some subgraph of G after contracting edges. The derivation of a polynomial-time algorithm for H-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. H-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) 19], providing an algorithm that in time O(3k2·(h+k-1)!·m) decides if a graph G with m edges and branchwidth k, contains a fixed graph H on h vertices as a minor. In this work we improve the dependence on k of Hicks' result by showing that checking if H is a minor of G can be done in time O(2(2k+1)·logk·h 2k·22h2·m). We set up an approach based on a combinatorial object called rooted packing, which captures the properties of the subgraphs of H that we seek in our dynamic programming algorithm. This formulation with rooted packings allows us to speed up the algorithm when G 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 2O(k)·h2k·2O(h)·n, with n=|V(G)|. 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.

Original languageEnglish (US)
Pages (from-to)7018-7028
Number of pages11
JournalTheoretical Computer Science
Issue number50
StatePublished - Nov 25 2011


  • Branchwidth
  • Dynamic programming
  • Graph minor containment
  • Graph minors
  • Graphs on surfaces
  • Parameterized complexity

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Faster parameterized algorithms for minor containment'. Together they form a unique fingerprint.

Cite this