13 Counting dominating sets
This section shows how the smaller pathwidth bounds speed up an algorithm that counts dominating sets by branching first and then switching to dynamic programming: with the new bounds, the switch can come one step earlier. We start from the exponential-space algorithm of Nederlof, van Rooij and van Dijk (Nederlof, Rooij, and Dijk 2014) for counting dominating sets in general graphs. It counts set covers by branching, and switches to dynamic programming over a path decomposition of the incidence graph once the instance is sparse. Its stated running time is \(O(1.5002^n)\). We prove the following theorem.
Theorem 13.1 (counting dominating sets). The numbers of dominating sets of each size of an \(n\)-vertex graph can be computed deterministically in time and space \(O(1.4815^n)\). If the vertices carry real weights with \(n^{O(1)}\) distinct subset sums, the same holds for the numbers of dominating sets of each size and each weight.
Our algorithm is the one of Nederlof, van Rooij and van Dijk with two changes. First, it switches to dynamic programming one step earlier, when all non-exceptional sets have size at most \(4\) instead of \(3\). Second, it uses a longer list of exceptional configurations.
While rerunning the original analysis we found a gap in it: one family of branching cases is not covered by the previous recurrences, and with the previous weights some of these cases violate the claimed branching factor. The gap is in the proof, not in the algorithm: re-optimizing the weights with all cases included shows that the original algorithm runs in time \(O(1.5004^n)\) (Proposition D.10). Appendix D.5 describes the gap; our analysis uses the corrected set of recurrences.
13.1 The algorithm
Set cover formulation.
A set cover instance consists of a finite universe \(\mathcal U\) of elements, a finite family \(\mathcal S\) of subsets of \(\mathcal U\) called sets, and a multiplicity \(\operatorname{mult}(s)\ge1\) for every \(s\in\mathcal S\); a set \(s\) stands for \(\operatorname{mult}(s)\) interchangeable copies. A cover of size \(\ell\) is a choice of \(\ell\) copies, of possibly several sets, whose union is \(\mathcal U\). The task is to compute the numbers \(c_\ell\) of covers of size \(\ell\) for all \(\ell\). The incidence graph \(I\) of the instance is the bipartite graph on \(\mathcal S\cup\mathcal U\) in which \(s\in\mathcal S\) and \(e\in\mathcal U\) are adjacent when \(e\in s\). We write \(d(s)=d_I(s)=|s|\) for the size of a set and \(d(e)=d_I(e)\) for the frequency of an element (the number of sets containing it), and \(N_I(e)\) for the sets containing \(e\). In the thesis and in the journal version, sets and elements are the red and blue vertices of a red-blue graph; this is the same object.
A graph \(G\) gives the instance with \(\mathcal U=V(G)\) and one set \(N[v]\) of multiplicity one for each \(v\in V(G)\) (true twins \(u,v\), with \(N[u]=N[v]\), give two identical sets, which the first reduction rule below merges). A vertex set \(D\) is dominating if and only if the copies \(\{N[v]:v\in D\}\) form a cover, so \(c_\ell\) is the number of dominating sets of size \(\ell\).
Exceptional configurations.
The algorithm leaves certain elements of frequency \(5\) to the dynamic program. The type of an element \(e\) of frequency \(5\) all of whose sets have size at most \(5\) is the tuple \((r_1,\dots,r_5)\), where \(r_i\) is the number of sets of size \(i\) containing \(e\); thus \(r_1+\dots+r_5=5\). (Here and below, \(r_i\) counts neighbors of a vertex of \(I\) by degree; it is unrelated to the domain size \(r\) of Section 11.) Let \(\mathcal X\) be a list of types and \(\sigma\in\{3,4\}\). An element is exceptional if it has frequency \(5\) and its type is in \(\mathcal X\). A set is exceptional if its size lies in \(\{\sigma+1,\dots,5\}\) and it contains an exceptional element. We always assume \[\begin{equation*} \tag{13.1} r_i=0\ \text{ for } i>\sigma+1 \text{ and } r_1\le1 \quad\text{for every type } (r_1,\dots,r_5)\in\mathcal X, \end{equation*}\] so that every set that contains an exceptional element has size at most \(\sigma+1\); in particular, every exceptional set has size exactly \(\sigma+1\).
The previous algorithm has \(\sigma=3\) and the list \(\mathcal X_{14}\) of fourteen types of Table 6 (Rooij 2011 Overview 8.1, p. 150), (Nederlof, Rooij, and Dijk 2014 Overview 1, p. 727); with it, exceptional sets have size \(4\). Our algorithm has \(\sigma=4\) and the list \(\mathcal X_{30}\), which adds sixteen types with \(r_1=1\). Both lists satisfy (13.1): the types of \(\mathcal X_{14}\) have \(r_5=0\), and those of \(\mathcal X_{30}\) have no set of size above \(5\).
Table 6: Types \((r_1,\dots,r_5)\) of exceptional elements of frequency \(5\). The previous list \(\mathcal X_{14}\) (Nederlof, Rooij, and Dijk 2014 Overview 1) and the sixteen types added in \(\mathcal X_{30}\).
| \(\mathcal X_{14}\) | (1,4,0,0,0), (1,3,1,0,0), (1,2,2,0,0), (1,1,3,0,0), (1,0,4,0,0), (1,3,0,1,0), (1,2,1,1,0), (0,5,0,0,0), (0,4,1,0,0), (0,3,2,0,0), (0,2,3,0,0), (0,1,4,0,0), (0,4,0,1,0), (0,3,1,1,0) |
|---|---|
| added in \(\mathcal X_{30}\) | (1,0,0,4,0), (1,0,1,3,0), (1,0,2,1,1), (1,0,2,2,0), (1,0,3,0,1), (1,0,3,1,0), (1,1,0,2,1), (1,1,0,3,0), (1,1,1,1,1), (1,1,1,2,0), (1,1,2,0,1), (1,1,2,1,0), (1,2,0,1,1), (1,2,0,2,0), (1,2,1,0,1), (1,3,0,0,1) |
The algorithm \(\mathcal A_{\sigma,\mathcal X}\).
On an instance \((\mathcal S,\mathcal U,\operatorname{mult})\) the algorithm applies the first applicable rule of the following list and recurses. We write \(C(\cdot)\) for the vector \((c_\ell)_\ell\) returned by a recursive call, and \[\begin{equation*} \tag{13.2} \operatorname{take}_s(C)_\ell=\sum_{i=1}^{\operatorname{mult}(s)}\binom{\operatorname{mult}(s)}{i}\,c_{\ell-i} \end{equation*}\] for the correction that accounts for choosing at least one of the copies of a set \(s\) (with \(c_j=0\) for \(j<0\)) (Nederlof, Rooij, and Dijk 2014 Proposition 26).
(R1) Identical sets. If two sets \(s_1\ne s_2\) have the same elements, delete \(s_2\) and set \(\operatorname{mult}(s_1):=\operatorname{mult}(s_1)+\operatorname{mult}(s_2)\).
(R2) Forced set. If an element has frequency \(1\), let \(s\) be its set; return \(\operatorname{take}_s(C(\mathcal S\setminus\{s\},\mathcal U\setminus s))\), where every remaining set loses its elements in \(s\).
(R3) Subsumed element. If two elements \(e_1\ne e_2\) satisfy \(N_I(e_1)\subseteq N_I(e_2)\) (every set containing \(e_1\) contains \(e_2\)), delete \(e_2\) from \(\mathcal U\) and from all sets.
If no reduction rule applies, let \(s\) be a non-exceptional set of maximum size and \(e\) a non-exceptional element of maximum frequency (with \(d(s)=0\) or \(d(e)=0\) if there is none).
(A) Switch. If \(d(s)\le\sigma\) and \(d(e)\le4\), compute a path decomposition of \(I\) and count the covers by dynamic programming over it.
(B) Branch on a set. Otherwise, if \(d(s)>d(e)\) or \(d(e)\le4\), return \(\operatorname{take}_s(C(\mathcal S\setminus\{s\},\mathcal U\setminus s))+ C(\mathcal S\setminus\{s\},\mathcal U)\) (take \(s\), or discard it).
(C) Branch on an element. Otherwise return \(C(\mathcal S,\mathcal U\setminus\{e\})-C(\mathcal S\setminus N_I(e),\mathcal U\setminus\{e\})\) (make \(e\) optional, minus forbid \(e\)).
This is (Rooij 2011 Algorithm 8.2, p. 148) and (Nederlof, Rooij, and Dijk 2014 Algorithm 4, p. 725) when \(\sigma=3\) and \(\mathcal X=\mathcal X_{14}\); there, the switch is line 11 and line 12, respectively. The order of the reduction rules plays no role in the analysis.
How the switch works. The algorithm monitors two quantities: the largest size of a non-exceptional set and the largest frequency of a non-exceptional element. While either is large, branching on that set or element lowers the measure (13.3) defined below by a large amount in both branches. Once both are small, each further branching would lower the measure only a little, but the incidence graph is then sparse (maximum degree \(5\), with the vertices of degree \(5\) confined to the exceptional configurations), and its pathwidth is small. The threshold \(\sigma\) decides whether sets of size \(\sigma+1\) are branched on or handed to the dynamic program. The previous threshold \(\sigma=3\) branches on sets of size \(4\); we take \(\sigma=4\) and hand them to the dynamic program. The exceptional configurations make the same choice for elements of frequency \(5\): branching on an element whose sets are mostly very small lowers the measure only a little, and the dynamic program handles such an element at little extra running time.
Lemma 13.2 (correctness). For every \(\sigma\in\{3,4\}\) and every list \(\mathcal X\), the algorithm \(\mathcal A_{\sigma,\mathcal X}\) terminates and returns \((c_\ell)_\ell\), the numbers of covers of each size.
Proof. Every rule produces instances with fewer vertices in the incidence graph, so the recursion terminates. Correctness follows by induction on \(|V(I)|\); we check each rule in turn. (R1): a choice of copies of \(s_1\) and \(s_2\) is a choice of copies of the merged set, with the same union. (R2): every cover contains a copy of \(s\); covers containing \(i\ge1\) copies of \(s\) correspond to a choice of \(i\) of the \(\operatorname{mult}(s)\) copies together with a cover of \(\mathcal U\setminus s\) by the other sets, which gives (13.2). (R3): every cover contains a copy of a set containing \(e_1\), which contains \(e_2\); so a choice of copies covers \(\mathcal U\) if and only if it covers \(\mathcal U\setminus\{e_2\}\). (B): covers either contain a copy of \(s\) (counted as in (R2)) or none. (C): a choice of copies that covers \(\mathcal U\setminus\{e\}\) either covers \(e\) or uses no set containing \(e\), and the latter choices are exactly the covers of \(\mathcal U\setminus\{e\}\) by \(\mathcal S\setminus N_I(e)\); so the number of covers of \(\mathcal U\) of each size is the difference. (A): the dynamic program over a path decomposition of width \(p\) counts the covers of each size, with multiplicities, for every instance, in time \(O^*(2^{p})\) (Rooij 2011 Proposition 8.10), (Nederlof, Rooij, and Dijk 2014 Proposition 27); vertices of degree \(0\) of \(I\) (empty sets and elements of frequency \(0\)) are handled by a factor \((1+x)^{\operatorname{mult}(s)}\) in the size-generating function, or by returning \(0\). ∎
The measure.
The analysis measures an instance by \[\begin{equation*} \tag{13.3} k=\sum_{e\in\mathcal U}v\bigl(d(e)\bigr)+\sum_{s\in\mathcal S}w\bigl(d(s)\bigr), \end{equation*}\] where merged sets count once. The weights satisfy the following conditions, which are those of the thesis (Rooij 2011, 151); write \(\Delta v(i)=v(i)-v(i-1)\) and \(\Delta w(i)=w(i)-w(i-1)\).
(W1) \(v(0)=v(1)=w(0)=0\); \(v(i)=v(7)\) and \(w(i)=w(7)\) for \(i\ge7\); \(v(2)>0\) and \(w(1)>0\).
(W2) \(\Delta v(i)\ge0\) for \(i\ge2\) and \(\Delta w(i)\ge0\) for \(i\ge1\).
(W3) \(\Delta v(i)\ge\Delta v(i+1)\) for \(i\ge2\) and \(\Delta w(i)\ge\Delta w(i+1)\) for \(i\ge1\).
(W4) \(2\,\Delta v(5)\le v(2)\).
By (W1)–(W2) the weights are nonnegative and nondecreasing, so none of (R1)–(R3) increases the measure: each deletes vertices of \(I\) and lowers sizes or frequencies of others. A graph with \(n\) vertices gives an instance of measure at most \((v(7)+w(7))\,n\).
13.2 Outline of the analysis
The running-time analysis follows the measure-and-conquer scheme of the thesis (Rooij 2011, sec. 8.5) in three steps, which Appendix D carries out for both thresholds at once. First, branching recurrences bound the number of instances of each measure on which the dynamic program is called (Rooij 2011 Lemma 8.11); the branching vectors of degree above \(9\) reduce to those of degree at most \(9\). Second, a linear program in the numbers of sets and elements of each degree bounds the pathwidth of these instances (Rooij 2011 Lemma 8.12); its objectives are the pathwidth bounds of Part I, applied to the incidence graph. Third, the two bounds combine into the running time \(\alpha^{(v(7)+w(7))n}n^{O(1)}\) whenever \(2^L<\alpha\) for the value \(L\) of the linear program (Rooij 2011 Theorem 8.13).
For \(\mathcal A_{4,\mathcal X_{30}}\) we take \(\alpha=\frac{13}{10}\) and rational weights with \(v(7)+w(7)=1.4980028\) (Table 12). All \(30{,}972\) branching vectors of degree at most \(9\) hold at \(\alpha\), the linear program has value \(L\approx0.37851\) with \(2^L<\alpha\), and \(\alpha^{1.4980028}<1.4815\). Each of these steps is checked in exact rational or interval arithmetic. The decisive input is the coefficient \(\frac14\) of Theorem 1.3 at degree \(4\), in place of the \(\frac13\) of Fomin, Gaspers, Saurabh and Stepanov (Fomin et al. 2009 Lemma 1): the worst instances of the linear program are close to incidence graphs of cubic graphs. For the weighted counts, the multiplicity of a set becomes a generating polynomial in size and weight, and the measure and running time are those of the unweighted case (Appendix D.3).