Fast Algorithms for Join Operations on Tree Decompositions

Abstract

Treewidth is a measure of how tree-like a graph is. It has many important algorithmic applications because many NP-hard problems on general graphs become tractable when restricted to graphs of bounded treewidth. Algorithms for problems on graphs of bounded treewidth mostly are dynamic programming algorithms using the structure of a tree decomposition of the graph. The bottleneck in the worst-case run time of these algorithms often is the computations for the so called join nodes in the associated nice tree decomposition. In this paper, we review two different approaches that have appeared in the literature about computations for the join nodes: one using fast zeta and Möbius transforms and one using fast Fourier transforms. We combine these approaches to obtain new, faster algorithms for a broad class of vertex subset problems known as the [σ,ρ] -domination problems. Our main result is that we show how to solve [σ,ρ]-domination problems in O(st+2tn2(tlog(s)+log(n))) arithmetic operations. Here, t is the treewidth, s is the (fixed) number of states required to represent partial solutions of the specific [σ,ρ]-domination problem, and n is the number of vertices in the graph. This reduces the polynomial factors involved compared to the previously best time bound (van Rooij, Bodlaender, Rossmanith, ESA 2009) of O(st+2(st)2(s−2)n3) arithmetic operations. In particular, this removes the dependence of the degree of the polynomial on the fixed number of states s.