Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth

H.L. Bodlaender, M. Cygan, S. Kratsch, J. Nederlof

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

36 Citaten (Scopus)
1 Downloads (Pure)

Samenvatting

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.
Originele taal-2Engels
TitelAutomata, Languages, and Programming (40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part I)
RedacteurenF.V. Fomin, R. Freivalds, M. Kwiatkowska, D. Peleg
Plaats van productieBerlin
UitgeverijSpringer
Pagina's196-207
ISBN van geprinte versie978-3-642-39205-4
DOI's
StatusGepubliceerd - 2013
Extern gepubliceerdJa
Evenement40th International Colloquium on Automata, Languages, and Programming (ICALP 2013) - University of Latvijas, Riga, Letland
Duur: 8 jul 201312 jul 2013
Congresnummer: 40
http://www.icalp2013.lu.lv/

Publicatie series

NaamLecture Notes in Computer Science
Volume7965
ISSN van geprinte versie0302-9743

Congres

Congres40th International Colloquium on Automata, Languages, and Programming (ICALP 2013)
Verkorte titelICALP 2013
Land/RegioLetland
StadRiga
Periode8/07/1312/07/13
Ander40th International Colloquium on Automata, Languages, and Programming
Internet adres

Vingerafdruk

Duik in de onderzoeksthema's van 'Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth'. Samen vormen ze een unieke vingerafdruk.

Citeer dit