skip to main content

Deterministic Single Exponential Time Algorithms for Connectivity Problems Parameterized by Treewidth

Bodlaender, H. L. ; Cygan, M. ; Kratsch, S. ; Nederlof, J. Fomin, F. V. ; Freivalds, F. ; Kwiatkowska, M. Z. ; Peleg, D.

2013

Texto completo disponível

Citações Citado por
  • Título:
    Deterministic Single Exponential Time Algorithms for Connectivity Problems Parameterized by Treewidth
  • Autor: Bodlaender, H. L. ; Cygan, M. ; Kratsch, S. ; Nederlof, J.
  • Fomin, F. V. ; Freivalds, F. ; Kwiatkowska, M. Z. ; Peleg, D.
  • Descrição: It is well known that many local graph problems, like Vertex Cover and Dominating Set, can be solved in 2O(tw)nO(1) time for graphs with a given tree decomposition of width tw. However, for nonlocal problems, like the fundamental class of connectivity problems, for a long time it was unknown how to do this faster than twO(tw)nO(1) until recently, when Cygan et al. (FOCS 2011) introduced the Cut&Count technique that gives randomized algorithms for a wide range of connectivity problems running in time ctwnO(1) for a small constant c. In this paper, we show that we can improve upon the Cut&Count technique in multiple ways, with two new techniques. The first technique (rank-based approach) gives deterministic algorithms with O(c tw n) running time for connectivity problems (like Hamiltonian Cycle and Stei-ner Tree) and for weighted variants of these; the second technique (determinant approach) gives deterministic algorithms running in time ctwnO(1) for counting versions, e.g., counting the number of Hamiltonian cycles for graphs of treewidth tw. The rank-based approach introduces a new technique to speed up dynamic programming algorithms which is likely to have more applications. The determinant-based approach uses the Matrix Tree Theorem for deriving closed formulas for counting versions of connectivity problems; we show how to evaluate those formulas via dynamic programming.
  • Data de publicação: 2013
  • Idioma: Inglês

Buscando em bases de dados remotas. Favor aguardar.