TY - GEN
T1 - Faster parameterized algorithms for minor containment
AU - Adler, Isolde
AU - Dorn, Frederic
AU - Fomin, Fedor V.
AU - Sau, Ignasi
AU - Thilikos, Dimitrios M.
PY - 2010
Y1 - 2010
N2 - The theory of Graph Minors by Robertson and Seymour is one of the deepest and significant theories in modern Combinatorics. This theory has also a strong impact on the recent development of Algorithms, and several areas, like Parameterized Complexity, have roots in Graph Minors. Until very recently it was a common belief that Graph Minors Theory is mainly of theoretical importance. However, it appears that many deep results from Robertson and Seymour's theory can be also used in the design of practical algorithms. Minor containment testing is one of algorithmically most important and technical parts of the theory, and minor containment in graphs of bounded branchwidth is a basic ingredient of this algorithm. In order to implement minor containment testing on graphs of bounded branchwidth, Hicks [NETWORKS 04] described an algorithm, that in time script 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. That algorithm follows the ideas introduced by Robertson and Seymour in [J'CTSB 95]. 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 script O(2 (2k+1)·log k·h2k·2 2h2·m). Our approach is based on a combinatorial object called rooted packing, which captures the properties of the potential models of 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 single-exponential algorithm for minor containment testing. Namely, it runs in time 2 script O(k)·h2k·2 script O(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 minor containment.
AB - The theory of Graph Minors by Robertson and Seymour is one of the deepest and significant theories in modern Combinatorics. This theory has also a strong impact on the recent development of Algorithms, and several areas, like Parameterized Complexity, have roots in Graph Minors. Until very recently it was a common belief that Graph Minors Theory is mainly of theoretical importance. However, it appears that many deep results from Robertson and Seymour's theory can be also used in the design of practical algorithms. Minor containment testing is one of algorithmically most important and technical parts of the theory, and minor containment in graphs of bounded branchwidth is a basic ingredient of this algorithm. In order to implement minor containment testing on graphs of bounded branchwidth, Hicks [NETWORKS 04] described an algorithm, that in time script 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. That algorithm follows the ideas introduced by Robertson and Seymour in [J'CTSB 95]. 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 script O(2 (2k+1)·log k·h2k·2 2h2·m). Our approach is based on a combinatorial object called rooted packing, which captures the properties of the potential models of 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 single-exponential algorithm for minor containment testing. Namely, it runs in time 2 script O(k)·h2k·2 script O(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 minor containment.
KW - branchwidth
KW - dynamic programming
KW - Graph minors
KW - graphs on surfaces
KW - parameterized complexity
UR - http://www.scopus.com/inward/record.url?scp=77954652159&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=77954652159&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-13731-0_31
DO - 10.1007/978-3-642-13731-0_31
M3 - Conference contribution
AN - SCOPUS:77954652159
SN - 364213730X
SN - 9783642137303
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 322
EP - 333
BT - Algorithm Theory - SWAT 2010 - 12th Scandinavian Symposium and Workshops on Algorithm Theory, Proceedings
T2 - 12th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2010
Y2 - 21 June 2010 through 23 June 2010
ER -