Name
Title | ||
|---|---|---|
Solving weighted and counting variants of connectivity problems parameterized by treewidth deterministically in single exponential time |
Abstract | ||
|---|---|---|
It is well known that many local graph problems, like Vertex Cover and Dominating Set, can be solved in 2^{O(tw)}|V|^{O(1)} time for graphs G=(V,E) with a given tree decomposition of width tw. However, for nonlocal problems, like the fundamental class of connectivity problems, for a long time we did not know how to do this faster than tw^{O(tw)}|V|^{O(1)}. Recently, Cygan et al. (FOCS 2011) presented Monte Carlo algorithms for a wide range of connectivity problems running in time $c^{tw}|V|^{O(1)} for a small constant c, e.g., for Hamiltonian Cycle and Steiner tree. Naturally, this raises the question whether randomization is necessary to achieve this runtime; furthermore, it is desirable to also solve counting and weighted versions (the latter without incurring a pseudo-polynomial cost in terms of the weights). We present two new approaches rooted in linear algebra, based on matrix rank and determinants, which provide deterministic c^{tw}|V|^{O(1)} time algorithms, also for weighted and counting versions. For example, in this time we can solve the traveling salesman problem or count the number of Hamiltonian cycles. The rank-based ideas provide a rather general approach for speeding up even straightforward dynamic programming formulations by identifying "small" sets of representative partial solutions; we focus on the case of expressing connectivity via sets of partitions, but the essential ideas should have further 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. |
Year | Venue | Field |
|---|---|---|
2012 | CoRR | Rank (linear algebra),Discrete mathematics,Combinatorics,Dominating set,Parameterized complexity,Hamiltonian path,Steiner tree problem,Tree decomposition,Vertex cover,Treewidth,Mathematics |
DocType | Volume | Citations |
Journal | abs/1211.1505 | 8 |
PageRank | References | Authors |
0.59 | 19 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hans L. Bodlaender | 1 | 5699 | 375.15 |
| Marek Cygan | 2 | 556 | 40.52 |
| Stefan Kratsch | 3 | 561 | 42.59 |
| Jesper Nederlof | 4 | 294 | 24.22 |