Elsevier

Information and Computation

Volume 243, August 2015, Pages 86-111
Information and Computation

Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth

https://doi.org/10.1016/j.ic.2014.12.008Get rights and content
Under an Elsevier user license
open archive

Abstract

It is well known that many local graph problems, like Vertex Cover and Dominating Set, can be solved in time 2O(tw)|V|O(1) 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 twO(tw)|V|O(1). Recently, Cygan et al. (FOCS 2011) presented Monte Carlo algorithms for a wide range of connectivity problems running in time ctw|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 the runtime in terms of the weights).

We present two new approaches rooted in linear algebra, based on matrix rank and determinants, which provide deterministic ctw|V|O(1) time algorithms, also for weighted and counting versions. For example, in this time we can solve Traveling Salesman  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.

Cited by (0)

A preliminary version of this work appeared at ICALP 2013 [1]. The second author was partially supported by NCN DEC-2012/05/D/ST6/03214 and Foundation for Polish Science. The third author was supported by the Nederlandse Organisatie voor Wetenschappelijk Onderzoek (NWO), project: ‘KERNELS’. The fourth author was supported by the Nederlandse Organisatie voor Wetenschappelijk Onderzoek (NWO), project: ‘Space and Time Efficient Structural Improvements of Dynamic Programming Algorithms’.