Faster parameterized algorithms for minor containment |
| |
Authors: | Isolde Adler Dimitrios M Thilikos |
| |
Affiliation: | a Institut für Informatik, Goethe-Universität, Frankfurt, Germanyb Department of Informatics, University of Bergen, Norwayc AlGCo project-team, CNRS, LIRMM, Montpellier, Franced Department of Mathematics, National and Kapodistrian University of Athens, Greece |
| |
Abstract: | 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) 1-9], 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⋅h2k⋅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. |
| |
Keywords: | Graph minors Branchwidth Graph minor containment Parameterized complexity Dynamic programming Graphs on surfaces |
本文献已被 ScienceDirect 等数据库收录! |
|