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 ). 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 many states. This does not quite work, however: consider a grid graph like the following:

…

Here, tells us nothing about whether and are connected somewhere within (ie. through ) or outside (through ). Subsequently we will not be able to ensure that and 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 ), the dependence on the treewidth is no longer singly exponential.

The Cut&Count technique 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 mod 2, but this seems hard. Computing the parity of is easy (in fact computing the whole of is easy), but this will not be very useful as the parity of and 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 such that no edge in crosses the cut. Equi­valently, a consistent cut consists of an assignment of a side (“left” or “right”) to each connected component of , and thus the number of consistent cuts is exactly , where 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 is connected and even otherwise. So let

Then , since connected potential solutions² contribute by exactly to all other potential solutions contribute by .

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 we may use standard DP techniques: Given a bag , a subset and an assignment , let be the number of pairs in except restricted to such that and gives the side of each vertex in in the cut, requiring that . Computing in time should then be relatively straightforward.

The promised proof of why parity is enough

There is some theorem that implies that randomly weighting the vertices in the graph and then looking for solutions that sum up to a given weight is enough.

Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magnam aliquam quaerat voluptatem. Ut enim aeque doleamus animo, cum corpore dolemus, fieri tamen permagna accessio potest, si aliquod aeternum et infinitum impendere malum nobis opinemur. Quod idem licet transferre in voluptatem, ut.