skip to main content

Faster parameterized algorithms for minor containment

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

Theoretical Computer Science, 2011, Vol.412(50), pp.7018-7028 [Periódico revisado por pares]

Texto completo disponível

Citações Citado por
  • Título:
    Faster parameterized algorithms for minor containment
  • Autor: Adler, Isolde ; Dorn, Frederic ; Fomin, Fedor V. ; Sau, Ignasi ; Thilikos, Dimitrios M.
  • Assuntos: Graph Minors ; Branchwidth ; Graph Minor Containment ; Parameterized Complexity ; Dynamic Programming ; Graphs on Surfaces
  • É parte de: Theoretical Computer Science, 2011, Vol.412(50), pp.7018-7028
  • Descrição: 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 ( 3 k 2 ⋅ ( 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 ( 2 k + 1 ) ⋅ log k ⋅ h 2 k ⋅ 2 2 h 2 ⋅ 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 2 O ( k ) ⋅ h 2 k ⋅ 2 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 containment.
  • Idioma: Inglês

Buscando em bases de dados remotas. Favor aguardar.