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 ; Computer Science ; Mathematics
  • É parte de: Theoretical Computer Science, 2011, Vol.412(50), pp.7018-7028
  • Descrição: The - 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 - 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. - 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 , 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.
  • Idioma: Inglês

Buscando em bases de dados remotas. Favor aguardar.