Enclsoing the horse in singly-exponential time

Consider the Steiner Tree problem:

Without the connectivity requirement, this problem can easily be solved by standard DP techniques (although it is also trivial: Just output yes if and only if $\left|𝑇\right|\le 𝑘$). When trying to formulate a treewidth-based DP for the full problem, however, we run into an issue: A naive formulation might look as follows:

with $𝑛2^{\text{tw}}$ many states. This does not quite work, however: consider a grid graph like the following:

Here, $𝐴\left(\text{row}3,\left\{\left(3,1\right),\left(3,3\right)\right\}\right)$ tells us nothing about whether $\left(3,1\right)$ and $\left(3,3\right)$ are connected somewhere within ${𝑉}_{\text{row}3}$ (ie. through $\left(4,2\right)$) or outside (through $\left(2,2\right)$). Subsequently we will not be able to ensure that $\left(3,1\right)$ and $\left(3,3\right)$ are connected at all!

The “simple” way to work around this is to represent which subsets of ${𝐵}_{𝑥}$ are connected in ${𝑉}_{𝑥}$ directly in the DP state itself, ie.

And while this works (and leads to a running time of the form $2^{𝑂\left(\text{tw}log\text{tw}\right)}𝑛$), the dependence on the treewidth is no longer singly exponential.

The Cut&Count technique [3] is a recent (2013) technique invented to solve problems with “connectivity constraints” such as the above in singly-exponential time.

Cut&Count

It will turn out that, instead of finding an exact answer, it will be sufficient to count the number of solutions (of a slightly modified problem) modulo 2. (proof of this comes later). As is usual whenever a DP gets too complicated, we will also take the solution size as a parameter $𝑘$ instead of computing the optimum directly.

Let $𝑅$ be the set of all “solutions” of the given size without the con­nectivity constraint (we will call these “potential solutions”), and $𝑆$ be the subset of potential solutions which are actually connected.

We would like to compute $\left|𝑆\right|$ mod 2, but this seems hard. Computing the parity of $\left|𝑅\right|$ is easy (in fact computing the whole of $\left|𝑅\right|$ is easy), but this will not be very useful as the parity of $\left|𝑆\right|$ and $\left|𝑅\right|$ may differ.¹

The main idea of the Cut&Count technique is to replace the “global” connectivity constraint with a local constraint about graph cuts. More specifically, consider some potential solution $𝑋$. Let a “consistent cut” of $𝑋$ be a cut $\left({𝑋}_{𝑙},{𝑋}_{𝑟}\right)$ such that no edge in $𝐺\left[𝑋\right]$ crosses the cut. Equi­valently, a consistent cut consists of an assignment of a side (“left” or “right”) to each connected component of $𝐺\left[𝑋\right]$, and thus the number of consistent cuts is exactly $2^{\text{cc}\left(𝐺\left[𝑋\right]\right)}$, where $\text{cc}\left(𝐻\right)$ is the number of con­nected components in $𝐻$.

This is almost what we want: if we somehow halved this number, we would get a number which is odd if $𝐺\left[𝑋\right]$ is connected and even otherwise. So let

Then $\left|𝐶\right|\equiv \left|𝑆\right|mod2$, since connected potential solutions² contribute by exactly $1$ to $\left|𝐶\right|$ all other potential solutions contribute by $0mod2$.

To halve this number, we may simply pick a vertex $𝑟$ we know is in the solution (ie. any vertex in $𝑇$) and require that it be put on the left side of the cut.

To compute $\left|𝐶\right|$ we may use standard DP techniques: Given a bag $𝑡$, a subset $𝑋\subset {𝐵}_{𝑡}$ and an assignment $𝑠:𝐴\to \left\{\text{L},\text{R}\right\}$, let $𝑐\left(𝑡,𝐴,𝑠\right)$ be the number of pairs $\left(𝑋,\left({𝑋}_{𝑙},{𝑋}_{𝑟}\right)\right)$ in $𝐶$ except restricted to $𝐺\left[{𝑉}_{𝑡}\right]$ such that $𝑋\cap {𝐵}_{𝑡}=𝐴$ and $𝑠$ gives the side of each vertex in $𝐴$ in the cut, requiring that $𝑠\left(𝑟\right)=\text{L}$. Computing $𝑐$ in time ${𝑂}^{\ast }\left(2^{𝑂\left(𝑘\right)}\right)$ should then be relatively straightforward.

The promised proof of why parity is enough

The following definition and lemma are taken from [3]:

Definition. A function $𝜔:𝑈\to \mathbb{Z}$ isolates a set family $\mathrm{ℱ︀}\subseteq 2^{𝑈}$ if there is a unique ${𝑆}^{\prime }\in \mathrm{ℱ︀}$ with $𝜔\left({𝑆}^{\prime }\right)={min}_{𝑆\in \mathrm{ℱ︀}}𝜔\left(𝑆\right)$.

Lemma. (Isolation Lemma, [4]) Let $\mathrm{ℱ︀}\subseteq 2^{𝑈}$ be a set family over a universe $𝑈$ with $\left|\mathrm{ℱ︀}\right|>0$. For each $𝑢\in 𝑈$, choose a weight $𝜔\left(𝑢\right)\in \left\{1,2,\dots ,𝑁\right\}$ uniformly and independently at random. Then

The relevance of the Isolation Lemma is as follows: Let $𝑈=𝑉$ and $\mathrm{ℱ︀}$ be the set of solutions. Then the isolation lemma implies that if we randomly weigh the vertices in the graph, whp. there will be some weight $𝑤$ such that exactly one solution has weight $𝑤$. In particular, $1$ is odd, so if we only look for solutions of weight $𝑤$, if $𝜔\text{isolates}\mathrm{ℱ︀}$, we will detect that we have an odd number of solutions and thus that a solution exists.

We get the following algorithm: let $𝑁=2\left|𝑉\right|$, and uniformly and independently at random assign a weight in $\left\{1,\dots ,𝑁\right\}$ to each vertex in the graph. Then, for each $𝑤$ from $1$ to $𝑁\left|𝑉\right|$³, compute the number of solutions of total weight $𝑤mod2$. If any of them is nonzero, return True, otherwise return False.

Obviously, if the algorithm returns True, there must be at least one solution. Otherwise, the probability that a solution exists is $\le \left|𝑉\right|/𝑁=1/2$, by the Isolation Lemma, as outlined above.