Appendix D Counting dominating sets: the analysis
This appendix carries out the running-time analysis outlined in Section 13.2, in the notation of Section 13.1, and proves Theorem 13.1:
Theorem 13.1 (counting dominating sets; restated). 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.
Appendix D.1 proves the three steps of the analysis for a general threshold and list of exceptional types, Appendix D.2 applies them to \(\mathcal A_{4,\mathcal X_{30}}\), and Appendix D.3 treats the weighted counts. Appendix D.5 applies the analysis to the previous algorithm.
D.1 The three steps of the analysis
The analysis follows the measure-and-conquer scheme of the thesis, in three steps. First, a set of branching recurrences bounds the number of instances of each measure on which the dynamic program is called (Rooij 2011 Lemma 8.11) (Lemmas D.1, D.2 and D.3). Next, a linear program bounds the pathwidth of these instances (Rooij 2011 Lemma 8.12) (Lemmas D.4 and D.5). Finally, the two bounds are combined (Rooij 2011 Theorem 8.13) (Lemma D.6). We prove the three steps for both thresholds at once.
For \(a,b>0\) let \(\tau(a,b)\) be the unique \(x>1\) with \(x^{-a}+x^{-b}=1\), the branching factor of \((a,b)\). A vector \((a,b)\) holds at \(\alpha\) if \(\alpha^{-a}+\alpha^{-b}\le1\), that is, if \(\tau(a,b)\le\alpha\).
Branching vectors.
For \(d\ge5\) and \(r=(r_1,\dots,r_d)\) with \(\sum_ir_i=d\), \(r_1\le1\), and \((r_1,\dots,r_5)\notin\mathcal X\) when \(d=5\), the element vector \(E_{d,r}\) is \[\begin{equation*} \tag{D.1} \Bigl(v(d)+\sum_ir_i\,\Delta w(i),\ \ v(d)+\sum_ir_i\,w(i)+\Delta v(d)\sum_i(i-1)r_i\Bigr). \end{equation*}\] For \(d\ge\sigma+1\), \(f(d)=\max\{d-1,4\}\) and \(r=(r_2,\dots,r_{f(d)})\) with \(\sum_ir_i=d\), the set vector \(S_{d,r}\) is \[\begin{equation*} \tag{D.2} \Bigl(w(d)+\sum_ir_i\,\Delta v(i)+r_2\,w(1),\ \ w(d)+\sum_ir_i\,v(i)+\Delta w(d)\sum_i(i-1)r_i\Bigr). \end{equation*}\] These are the recurrences of (Rooij 2011, 152) and (Nederlof, Rooij, and Dijk 2014 Lemma 29, pp. 728–729), with the range of cases that the algorithm actually produces; Appendix D.5 shows that the previous range misses some of these cases.
Lemma D.1 (branching recurrences). Let \(\sigma\in\{3,4\}\), let \(\mathcal X\) satisfy (13.1), and let the weights satisfy (W1)–(W4). Whenever \(\mathcal A_{\sigma,\mathcal X}\) branches on an instance of measure \(k\), there is an element vector \((a,b)=E_{d,r}\) or a set vector \((a,b)=S_{d,r}\) such that the two child instances, after the reduction rules have been applied exhaustively, have measures at most \(k-a\) and \(k-b\).
Proof. Since the reduction rules do not increase the measure, it suffices to bound the measure right after the branching step, except for the term \(r_2w(1)\) in the set vector, which comes from reductions and is treated separately. When the algorithm branches, no reduction rule applies, so every element has frequency at least \(2\), distinct sets have distinct elements, and no two elements satisfy \(N_I(e_1)\subseteq N_I(e_2)\). We treat the two branching rules in turn. For each, we first bound the sizes and frequencies that can occur, which shows that the vector is one of those defined above, and then compute the decrease of the measure in the two branches.
Branching on an element \(e\) (rule (C)). Rule (B) did not apply, so \(d:=d(e)\ge5\) and \(d(s)\le d\). Every set containing \(e\) has size at most \(d\): non-exceptional sets have size at most \(d(s)\), and exceptional ones have size \(\sigma+1\le5\). Every element has frequency at most \(d\): non-exceptional ones by the choice of \(e\), exceptional ones have frequency \(5\). At most one set containing \(e\) has size \(1\), since two such sets would both equal \(\{e\}\). If \(d=5\), the type of \(e\) is not in \(\mathcal X\), since \(e\) is not exceptional. Let \(r_i\) be the number of sets of size \(i\) containing \(e\).
In the optional branch, \(e\) is deleted, which removes \(v(d)\), and each set containing \(e\) shrinks by one, which removes \(\Delta w(i)\) for a set of size \(i\) (a set of size \(1\) becomes empty and loses \(w(1)=\Delta w(1)\)). This is the first entry of (D.1). In the forbidden branch, \(e\) and the sets containing it are deleted, which removes \(v(d)+\sum_ir_iw(i)\), and every other element \(f\) of these sets loses frequency. The sets containing \(e\) have \(\sum_i(i-1)r_i\) incidences with other elements in total. We claim that an element of frequency \(j\) that loses \(t\ge1\) of its sets loses at least \(t\,\Delta v(d)\) in weight; summing over the elements gives the second entry. We have \(2\le j\le d\) and \(1\le t\le j\). If \(j-t\ge1\), then \(v(j)-v(j-t)=\sum_{l=j-t+1}^{j}\Delta v(l)\) with \(2\le l\le d\) (recall \(v(1)=0\)), and each term is at least \(\Delta v(d)\) by (W3). If \(j-t=0\), then \(t=j\) and \(v(j)-v(0)=v(2)+\sum_{l=3}^{j}\Delta v(l)\ge2\Delta v(d)+(j-2)\Delta v(d)=t\,\Delta v(d)\), using \(v(2)\ge2\Delta v(5)\ge2\Delta v(d)\) from (W4), (W3) and \(d\ge5\).
Branching on a set \(s\) (rule (B)). Let \(d=d(s)\). First, \(d\ge\sigma+1\): if \(d\le\sigma\), then either \(d(e)\le4\), and the switch (A) applies, or \(d(e)\ge5>d(s)\), and the algorithm branches on \(e\). Next, \(s\) contains no exceptional element: if \(d\le5\), a set of size in \(\{\sigma+1,\dots,5\}\) containing an exceptional element would be exceptional, and \(s\) is not; if \(d\ge6\), \(s\) cannot contain an exceptional element, because by (13.1) exceptional elements lie only in sets of size at most \(\sigma+1\le5\). Hence every element of \(s\) is non-exceptional and has frequency at most \(d(e)\). Since rule (B) applies, \(d(e)<d\) or \(d(e)\le4\), so every element of \(s\) has frequency in \(\{2,\dots,f(d)\}\). Every set has size at most \(d\): non-exceptional sets by the choice of \(s\), exceptional sets have size \(\sigma+1\le d\). Let \(r_i\) be the number of elements of \(s\) of frequency \(i\).
In the take branch, \(s\) and its elements are deleted, which removes \(w(d)+\sum_ir_iv(i)\), and every other set loses the elements it shares with \(s\); these are \(\sum_i(i-1)r_i\) incidences. A set of size \(j\le d\) that loses \(t\ge1\) elements loses \(w(j)-w(j-t)=\sum_{l=j-t+1}^{j}\Delta w(l)\ge t\,\Delta w(d)\), since \(1\le l\le d\) and (W3). This is the second entry of (D.2).
In the discard branch, \(s\) is deleted, which removes \(w(d)\), and each element of \(s\) of frequency \(i\) loses \(\Delta v(i)\) (for \(i=2\) this is \(v(2)\)). This gives \(w(d)+\sum_ir_i\Delta v(i)\) before reductions. Let \(E_2\) be the elements of \(s\) of frequency \(2\), and for \(e\in E_2\) let \(s_e\ne s\) be the other set containing \(e\). The sets \(s_e\) are distinct: if \(s_e=s_{e'}\) for \(e\ne e'\), then \(N_I(e)=\{s,s_e\}=N_I(e')\) before branching, and (R3) would have applied. We show that every \(s_e\) is deleted during the reductions that follow. Then the final measure is at most the measure before reductions minus \(\sum_{e\in E_2}w(d(s_e))\ge r_2w(1)\), because no weight increases during reductions, each \(s_e\) is a distinct vertex of weight at least \(w(1)\) before reductions, and it is absent at the end.
During these reductions no element reaches frequency \(0\): elements of \(s\) have frequency at least \(1\) after the discard; (R2) and (R3) delete elements but do not lower the frequency of the remaining ones; and (R1) lowers the frequency of an element only if it lies in two identical sets, leaving frequency at least \(1\). Suppose some \(s_e\) is never deleted. We may assume that it is never removed by (R1) either, by following the merged representative, which has the same elements. Then \(e\) is not deleted by (R2), since that would delete its only set \(s_e\). If \(e\) survives to the end, it has frequency \(1\) there, and (R2) would apply, a contradiction. So \(e\) is deleted by (R3), because of an element \(e_1\) with \(\emptyset\ne N_I(e_1)\subseteq N_I(e)=\{s_e\}\); then \(e_1\in s_e\) has frequency \(1\), and we repeat the argument with \(e_1\) in place of \(e\). As there are finitely many elements, this is a contradiction. So every \(s_e\) is deleted, which completes the proof of the first entry of (D.2). ∎
Lemma D.2 (high degrees). Assume (W1)–(W3). For every element or set vector of degree \(d\ge10\) there is a vector of the same kind and of degree \(d-1\) that is componentwise at most the given one. Hence, if every vector of degree at most \(9\) holds at \(\alpha\), then every vector holds at \(\alpha\).
Proof. By (W1), \(\Delta v(i)=\Delta w(i)=0\) and \(v(i)=v(7)\), \(w(i)=w(7)\) for \(i\ge8\).
Element vectors. Let \(d\ge10\). Delete one of the \(d\) neighbors from \(r\), and replace every remaining neighbor of size \(d\) by one of size \(d-1\); the result is a neighborhood \(r'\) of \(d-1\) sets of sizes at most \(d-1\) with \(r'_1\le r_1\le1\), so \(E_{d-1,r'}\) is an element vector (\(d-1\ge9>5\)). Since \(d-1\ge9\), the weights \(v(d)=v(d-1)\), \(\Delta v(d)=\Delta v(d-1)=0\), \(w(d)=w(d-1)\) and \(\Delta w(d)=\Delta w(d-1)=0\) do not change, and deleting a set of size \(i\) lowers the two entries by \(\Delta w(i)\ge0\) and \(w(i)\ge0\).
Set vectors. Let \(d\ge10\), so \(f(d)=d-1\) and \(f(d-1)=d-2\). Delete one element from \(r\) and replace every remaining element of frequency \(d-1\) by one of frequency \(d-2\); this gives a set vector \(S_{d-1,r'}\). Since \(d-2\ge8\), we have \(v(d-1)=v(d-2)\) and \(\Delta v(d-1)=\Delta v(d-2)=0\); also \(w(d)=w(d-1)\) and \(\Delta w(d)=\Delta w(d-1)=0\). Deleting an element of frequency \(i\) lowers the entries by \(\Delta v(i)\) (plus \(w(1)\) if \(i=2\)) and by \(v(i)\), both nonnegative.
Since \(\tau\) is decreasing in each argument, a vector componentwise at least a vector that holds at \(\alpha\) also holds at \(\alpha\); induction on \(d\) gives the last statement. ∎
The bound \(d\ge10\) cannot be lowered to \(d\ge9\) for set vectors: at \(d=9\), elements of frequency \(8\) would be replaced by elements of frequency \(7\), and \(\Delta v(7)>0=\Delta v(8)\), so the discard entry may increase. Vectors of degree \(9\) are therefore checked directly.
Lemma D.3 (leaves). Let \(\sigma\), \(\mathcal X\) and the weights be as in Lemma D.1, and let every element and set vector hold at \(\alpha>1\). For every instance \(J\) of measure \(k\) with incidence graph \(I\), the recursion tree of \(J\) has at most \(\alpha^{k-h}\) calls of the dynamic program on instances of measure \(h\), for every real \(h\ge0\), and at most \(2(1+|V(I)|)\) times as many nodes as leaves.
Proof. Let \(N_h\) be the number of calls of the dynamic program on instances of measure exactly \(h\) in the recursion tree of an instance \(J\) of measure \(k\). We show \(N_h\le\alpha^{k-h}\) by induction on the size of the recursion tree. If \(J\) is itself a leaf, \(N_h\le1\), and \(N_h=0\) unless \(k=h\). If \(J\) is reduced, its child has measure at most \(k\), and \(N_h\) is the same. If \(J\) branches, its two children, after reductions, have measures at most \(k-a\) and \(k-b\) by Lemma D.1, so \(N_h\le\alpha^{k-a-h}+\alpha^{k-b-h}\le\alpha^{k-h}\). For the second statement, every branching node has two children, so there are fewer branching nodes than leaves. The reduction steps form chains, each ending at a branching node or a leaf, so there are at most twice as many chains as leaves, and each chain has length at most \(|V(I)|\), since each step deletes a vertex. ∎
The instances handed to the dynamic program.
Let \(J\) be an instance on which the switch (A) applies, and let \(I\) be its incidence graph. Then every non-exceptional set has size at most \(\sigma\), every non-exceptional element has frequency at most \(4\), every exceptional element has frequency \(5\) and a type in \(\mathcal X\), and every set of size larger than \(\sigma\) is exceptional and has size \(\sigma+1\). In particular \(\Delta(I)\le5\). Let \(I'\) be obtained from \(I\) by deleting the sets of size \(1\) and the isolated vertices.
Lemma D.4 (pendant vertices). With \(I\) and \(I'\) as above, \(\mathop{\mathrm{pw}}(I)\le\mathop{\mathrm{pw}}(I')+1\).
Proof. Isolated vertices can be added as one-vertex bags. A set of size \(1\) is a vertex of degree \(1\) adjacent to its element \(f\). Take a path decomposition of \(I'\), and for each such vertex \(s\) choose a bag \(B\ni f\); insert directly after \(B\) the bag \(B\cup\{s\}\), and insert the bags for vertices attached at the same \(B\) one after another. Every new bag has at most \(|B|+1\) vertices, every edge \(sf\) is covered, and every vertex still occurs in consecutive bags. This is the argument of (Nederlof, Rooij, and Dijk 2014 Proposition 28) and (Rooij 2011 Remark 8.1). ∎
We now bound \(\mathop{\mathrm{pw}}(I')\) by pathwidth forms. A form is a nondecreasing function \(\varphi:\{1,\dots,5\}\to[0,1]\) such that every graph \(H\) without isolated vertices and with \(\Delta(H)\le5\) satisfies \[\begin{equation*} \tag{D.3} \mathop{\mathrm{pw}}(H)\le\sum_{x\in V(H)}\varphi\bigl(d_H(x)\bigr)+\rho_\varphi\bigl(|V(H)|\bigr) \end{equation*}\] with a remainder \(\rho_\varphi(t)=o(t)\), which we take nondecreasing (Section 4.1). A form is computable if for every such \(H\) a path decomposition of \(H\) of width at most the right side of (D.3) can be computed in polynomial time. We use the following forms, written as \((\varphi(1),\dots,\varphi(5))\); the decimal values are rational upper bounds for the constants, as used in the certificates below.
\(\varphi_{\mathsf{S}}=(0,0,\frac5{32},\frac14,\frac{11}{32})\), by Theorem 1.3 (or Theorem 7.2 with \(\mathsf{S}\));
\(\varphi_{\mathsf{R}}=(0,0,0.1455,0.2530,0.3600)\) and \(\varphi_{\mathsf{P}}=(0,0,0.140159,0.2575,0.3667)\), by Theorem 7.2, using \(F_3\le0.140159\) (Proposition 6.9);
\(\varphi_{a}=(F_4,F_4,F_4,F_4,1)\) with \(F_4\le0.24577197475\) (Proposition 6.9): by Theorem 7.1(a) applied to \(H-V_5\), where \(V_5\) is the set of vertices of degree \(5\), and \(\mathop{\mathrm{pw}}(H)\le\mathop{\mathrm{pw}}(H-V_5)+|V_5|\) (Section 4.1); Theorem 7.1(a) counts every vertex of \(H-V_5\), whatever its degree;
\(\varphi_{b}=(0,0,0.140159,0.2575,1)\): by Theorem 7.1(b) applied to \(H-V_5\);
\(\varphi_{3}=(0,0,0.139823,1,1)\): by Lemma 11.2 applied to \(H-V_{\ge4}\), where \(V_{\ge4}\) is the set of vertices of degree at least \(4\), with \(c_{3}\le0.139823\).
In the last three items, let \(X\) be the deleted set, \(V_5\) or \(V_{\ge4}\). The degrees in \(H-X\) are at most the degrees in \(H\), and the cited bounds have coefficients nondecreasing in the degree, so (D.3) holds with the degrees of \(H\). All these forms are computable: a decomposition of the stated width is computed deterministically in polynomial time by Theorem 10.1(b) or by Lemma 11.2, and in the last three items \(X\) is then added to all bags.
Assign to each vertex of \(I'\) a nominal degree: a set gets its size, a non-exceptional element its frequency, and an exceptional element of type \(c\) gets \(5-[c_1>0]\), its degree after the deletion of its set of size \(1\) (it has at most one). The nominal degree is at least the degree in \(I'\), since an element lies in at most one set of size \(1\) (two such sets would be identical); the two differ only for elements in a set of size \(1\). Since each form is nondecreasing and \(I'\) has no isolated vertices and maximum degree at most \(5\), \(\mathop{\mathrm{pw}}(I')\) is at most the sum of the form over the nominal degrees of the vertices of \(I'\), plus the remainder.
The linear program.
For a leaf instance of measure \(h>0\), divide the numbers of vertices of each kind by \(h\): let \(x_i\) (\(1\le i\le\sigma+1\)) be the scaled number of sets of size \(i\), \(y_i\) (\(2\le i\le4\)) that of non-exceptional elements of frequency \(i\), and \(e_c\) (\(c\in\mathcal X\)) that of exceptional elements of type \(c\). These numbers satisfy \[\begin{align*}\begin{equation*} \begin{aligned}&\sum_{i=1}^{\sigma+1}w(i)\,x_i+\sum_{i=2}^{4}v(i)\,y_i+v(5)\sum_{c}e_c=1,\end{aligned} \end{equation*}\tag{D.4}\\ \begin{equation*} \begin{aligned}&\sum_{i=1}^{\sigma+1}i\,x_i=\sum_{i=2}^{4}i\,y_i+5\sum_ce_c,\end{aligned} \end{equation*}\tag{D.5}\\ \begin{equation*} \begin{aligned}&\sum_c c_j\,e_c\le j\,x_j\qquad(1\le j\le\sigma+1),\end{aligned} \end{equation*}\tag{D.6}\\ \begin{equation*} \begin{aligned}&x_{\sigma+1}\le\sum_c c_{\sigma+1}\,e_c,\end{aligned} \end{equation*}\tag{D.7}\end{align*}\] and all variables are nonnegative. Here (D.4) is the measure (sets of size \(0\) and elements of frequency \(0\) have weight \(0\), and elements of frequency \(1\) do not occur), and (D.5) counts the edges of \(I\) from both sides. Inequality (D.6) holds because the \(\sum_cc_je_c\) incidences between exceptional elements and sets of size \(j\) are at most \(j\) per such set, and (D.7) holds because every set of size \(\sigma+1\) is exceptional and so contains an exceptional element.
For a form \(\varphi\) let \(\Phi_\varphi(x,y,e)\) be the sum of \(\varphi\) over the nominal degrees, scaled: \[\Phi_\varphi=\sum_{i=2}^{\sigma+1}\varphi(i)\,x_i+\sum_{i=2}^4\varphi(i)\,y_i +\sum_c\varphi\bigl(5-[c_1>0]\bigr)\,e_c ,\] where sets of size \(1\) contribute nothing. Let \(L(\sigma,\mathcal X,\Psi)\) be the maximum of \(\min_{\varphi\in\Psi}\Phi_\varphi\) over the polytope (D.4)–(D.7), for a set \(\Psi\) of forms. This is the linear program of (Rooij 2011 Lemma 8.12) and (Nederlof, Rooij, and Dijk 2014 Lemma 30, pp. 729–731), with several forms and with the constraints (D.6)–(D.7) for a general threshold.
Lemma D.5 (pathwidth at the switch). Let \(\sigma\), \(\mathcal X\) and the weights be as in Lemma D.1, let \(\Psi\) be a finite set of computable forms, and let \(L\ge L(\sigma,\mathcal X,\Psi)\). Then for every instance of measure \(h\) on which \(\mathcal A_{\sigma,\mathcal X}\) calls the dynamic program, a path decomposition of its incidence graph of width at most \(L\,h+o(h)\) can be computed in polynomial time, where the \(o(h)\) depends only on the weights and on \(\Psi\).
Proof. The scaled counts of a leaf instance are feasible, so \(\min_\varphi\Phi_\varphi\le L\), that is, \(\min_\varphi\sum_x\varphi(\cdot)\le Lh\) before scaling. By the discussion of nominal degrees and (D.3), \(\mathop{\mathrm{pw}}(I')\le Lh+\max_\varphi\rho_\varphi(|V(I')|)\), and \(\mathop{\mathrm{pw}}(I)\le\mathop{\mathrm{pw}}(I')+1\) by Lemma D.4. Every vertex of \(I'\) has weight at least \(\min\{v(2),w(1)\}>0\) in the measure, so \(|V(I')|\le h/\min\{v(2),w(1)\}\), and the remainder is \(o(h)\). The decomposition is the narrowest of those computed for the forms, followed by the insertions of Lemma D.4. ∎
Certificates for \(L\).
Write the program in terms of the vector \(z=(x,y,e)\): (D.4) as \(\mathbf m^{\top}z=1\), (D.5) as \(\mathbf a^{\top}z=0\), (D.6)–(D.7) as \(Bz\le0\), and \(\Phi_\varphi(z)=\mathbf f_\varphi^{\top}z\). By weak duality, a bound \(L\ge L(\sigma,\mathcal X,\Psi)\) is certified by \(\lambda_\varphi\ge0\) (\(\varphi\in\Psi\)) with \(\sum_\varphi\lambda_\varphi=1\), a real \(\mu\) and a vector \(\nu\ge0\) such that, componentwise, \[\begin{equation*} \tag{D.8} \sum_{\varphi\in\Psi}\lambda_\varphi\,\mathbf f_\varphi\le L\,\mathbf m+\mu\,\mathbf a+B^{\top}\nu . \end{equation*}\] Indeed, the inner product of (D.8) with a feasible point \(z\ge0\) gives \(\min_\varphi\Phi_\varphi(z)\le\sum_\varphi\lambda_\varphi\Phi_\varphi(z)\le L\,\mathbf m^{\top}z+\mu\,\mathbf a^{\top}z+\nu^{\top}Bz\le L\), since \(\nu\ge0\) and \(Bz\le0\).
Lemma D.6 (running time). Let \(\sigma\), \(\mathcal X\) and the weights be as in Lemma D.1, let \(\Psi\) be a finite set of computable forms, and let \(\alpha>1\) with \(2^{L(\sigma,\mathcal X,\Psi)}<\alpha\). If every branching vector of degree at most \(9\) holds at \(\alpha\), then \(\mathcal A_{\sigma,\mathcal X}\), with the dynamic program run on the narrowest decomposition of Lemma D.5, counts the dominating sets of each size of an \(n\)-vertex graph in time and space \(O\bigl(\alpha^{(v(7)+w(7))n}\,n^{O(1)}\bigr)\).
Proof. Fix a real \(L\ge L(\sigma,\mathcal X,\Psi)\) with \(2^L<\alpha\). By Lemma D.2 every branching vector holds at \(\alpha\), so by Lemma D.3 at most \(\alpha^{k-h}\) leaves have measure \(h\), where \(k\le(v(7)+w(7))n\) is the initial measure. By Lemma D.5 and the dynamic program, a leaf of measure \(h\) takes time \(2^{Lh+o(h)}n^{O(1)}\). Since \(2^{L}<\alpha\) and the remainder is \(o(h)\), there is a constant \(C\) with \(2^{Lh+o(h)}\le C\alpha^{h}\) for all \(h\ge0\). The measure is determined by the numbers of sets of each size \(1,\dots,7\) (sizes at least \(7\) together) and of elements of each frequency \(2,\dots,7\); these are at most \(2n\), so at most \((2n+1)^{13}\) values of \(h\) occur. Every vertex of the recursion tree costs polynomial time besides the dynamic program, and there are polynomially many nodes per leaf by Lemma D.3. Summing, \[T\le n^{O(1)}\sum_{h}\alpha^{k-h}\,C\,\alpha^{h}\le n^{O(1)}\,\alpha^{(v(7)+w(7))n}.\] The space is dominated by the tables of the dynamic program, at most \(2^{Lh+o(h)}n^{O(1)}\le C\alpha^{h}n^{O(1)}\) at a leaf of measure \(h\le k\). ∎
D.2 Proof of Theorem 13.1
The algorithm of Theorem 13.1 is \(\mathcal A_{4,\mathcal X_{30}}\). Compared with the previous one, it switches to dynamic programming when every non-exceptional set has size at most \(4\) (rather than \(3\)) and every non-exceptional element has frequency at most \(4\). Its exceptional elements are those with a type in \(\mathcal X_{30}\), and its exceptional sets are the sets of size \(5\) that contain one. The dynamic program runs on the narrowest of the path decompositions for the forms \(\Psi=\{\varphi_{\mathsf{S}},\varphi_{\mathsf{R}},\varphi_{\mathsf{P}},\varphi_a,\varphi_b,\varphi_3\}\) listed before Lemma D.5, computed by Theorem 10.1(b) and Lemma 11.2, instead of the decomposition of Fomin, Gaspers, Saurabh and Stepanov (Fomin et al. 2009 Lemma 1). Correctness is Lemma 13.2.
Table 12: Weights of the measure (13.3): previous ((Rooij 2011, 151), (Nederlof, Rooij, and Dijk 2014, 728)), certified for the previous algorithm with all cases (Proposition D.10), and certified for Theorem 13.1. All values are exact decimals; \(v(i)=v(7)\) and \(w(i)=w(7)\) for \(i\ge7\).
| \(i\) | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| previous \(v(i)\) | 0 | 0.275603 | 0.551206 | 0.658484 | 0.719009 | 0.745509 | 0.749538 |
| previous \(w(i)\) | 0.354816 | 0.625964 | 0.785112 | 0.923325 | 0.986711 | 1 | 1 |
| repaired \(v(i)\) | 0 | 0.2351251 | 0.4702502 | 0.5842398 | 0.6447407 | 0.6729014 | 0.6766715 |
| repaired \(w(i)\) | 0.3126782 | 0.5477033 | 0.6838767 | 0.8200501 | 0.8626895 | 0.8695487 | 0.8695487 |
| Theorem 13.1 \(v(i)\) | 0 | 0.2175171 | 0.4350342 | 0.5562242 | 0.6220752 | 0.6539177 | 0.6655099 |
| Theorem 13.1 \(w(i)\) | 0.3062246 | 0.5338365 | 0.6754745 | 0.7616247 | 0.8178813 | 0.8324929 | 0.8324929 |
Proof of Theorem 13.1 for unweighted counting. We apply Lemma D.6 with \(\sigma=4\), \(\mathcal X=\mathcal X_{30}\), \(\alpha=\frac{13}{10}\), the weights of Table 12 and the set \(\Psi\) of six computable forms above. Each step is checked by the accompanying code, as follows.
Weights. The weights are rational and satisfy (W1)–(W4), checked in exact rational arithmetic. Explicitly, the increments \[\begin{align*} (\Delta v(2),\dots,\Delta v(7))&=(0.2175171, 0.2175171, 0.1211900, 0.0658510, 0.0318425, 0.0115922),\\ (\Delta w(1),\dots,\Delta w(7))&=(0.3062246, 0.2276119, 0.1416380, 0.0861502, 0.0562566, 0.0146116, 0) \end{align*}\] are nonnegative and nonincreasing, and \(2\Delta v(5)=0.131702\le v(2)\). The list \(\mathcal X_{30}\) satisfies (13.1).
Branching. By Lemma D.1 the branching vectors are the element vectors \(E_{d,r}\) (\(d\ge5\)) and the set vectors \(S_{d,r}\) (\(d\ge5\), frequencies at most \(d-1\)). There are \(30{,}972\) of them of degree at most \(9\). Their entries are exact rationals; the code evaluates \(\alpha^{-a}+\alpha^{-b}\) in interval arithmetic (mpmath, 120-bit precision), and the largest upper end is \(0.999999610<1\). By Lemma D.2, every branching vector holds at \(\alpha\).
Dynamic programming. The code computes an exact rational solution of (D.8) for the program with \(\sigma=4\), \(\mathcal X_{30}\) and \(\Psi\), which certifies \(L(4,\mathcal X_{30},\Psi)\le L\) with \(L\approx0.378511274\), and \(2^{L}<1.2999997<\alpha\), by interval arithmetic. In floating point, the optimum is attained at \(x_4=y_4\approx0.7492\) with small amounts of sets of size \(2\) and \(3\) and of exceptional elements of type \((0,1,4,0,0)\); so the worst instances are close to incidence graphs of cubic graphs. The exact certificate puts weight only on \(\varphi_{\mathsf{S}}\) (Theorem 1.3) and \(\varphi_a\) (Theorem 7.1(a) after deleting the vertices of degree \(5\)), with \(\lambda_{\varphi_{\mathsf{S}}}=\frac{460610214}{535261133}\approx0.8605\) and \(\lambda_{\varphi_a}=\frac{74650919}{535261133}\approx0.1395\), so it also certifies the bound for these two forms alone; with \(\varphi_{\mathsf{S}}\) alone the value is \(0.3794062>\log_2\alpha\) in floating point.
Combination. By Lemma D.6 the running time is \(O(\alpha^{(v(7)+w(7))n}n^{O(1)})\) with \(v(7)+w(7)=1.4980028\), and \(\alpha^{1.4980028}<1.481452<1.4815\), which absorbs the polynomial factor. The algorithm is deterministic, since Theorem 10.1(b) and Lemma 11.2 are. ∎
Since the exact certificate puts weight only on \(\varphi_{\mathsf{S}}\) and \(\varphi_a\), it also certifies the bound with \(\Psi=\{\varphi_{\mathsf{S}},\varphi_a\}\); with this \(\Psi\) the proof uses, among the results of this paper, only Theorem 1.3, Theorem 7.1(a) and Theorem 10.1. The other forms are kept because adding a form to \(\Psi\) never raises \(L(\sigma,\mathcal X,\Psi)\), and its decomposition is computed in polynomial time.
D.3 Weighted versions
Let the vertices of \(G\) have real weights, and let the set \(\Sigma=\{\sum_{v\in X}\mathrm{wt}(v):X\subseteq V(G)\}\) of subset sums have size polynomial in \(n\). We count dominating sets by size and weight; the least weight with a nonzero count, and that count, solve Minimum Weight Dominating Set and #Minimum Weight Dominating Set. The algorithm and its measure stay the same; only the bookkeeping changes.
The difficulty is the identical-sets rule (R1): true twins of different weights give identical sets of different weights, so after merging a multiplicity no longer describes the copies. We therefore replace the multiplicity of a set \(s\) by the generating polynomial \[P_s(x,z)=\prod_{c}\bigl(1+x\,z^{\mathrm{wt}(c)}\bigr)-1\] of the nonempty selections of its copies \(c\) (vertices of \(G\)), by number (\(x\)) and weight (\(z\)); initially \(P_{N[v]}=x\,z^{\mathrm{wt}(v)}\). All copies have the same elements, so every nonempty selection covers the same elements. The algorithm returns a polynomial \(\sum_{\ell,\omega}c_{\ell,\omega}x^\ell z^\omega\), and the rules become:
(R1): the merged set gets \((1+P_{s_1})(1+P_{s_2})-1\);
(R2), the take branch of (B), and the dynamic program when it puts \(s\) into the solution: multiply by \(P_s\) in place of (13.2); discarding \(s\) multiplies by \(1\);
Correctness. Different sets have disjoint sets of copies, since the rules only merge or remove sets. Call a set \(Y\) of copies a cover if the sets of its copies have union \(\mathcal U\); its size is \(|Y|\) and its weight is \(\sum_{c\in Y}\mathrm{wt}(c)\). By induction on \(|V(I)|\), the algorithm returns the generating polynomial of the covers by size and weight; the recursion terminates, since every rule produces instances with fewer vertices of \(I\). The nonempty selections of copies of a set \(s\) have generating polynomial \(P_s\), and each covers exactly the elements of \(s\). (R1): a selection of copies of the merged set is a pair of selections of copies of \(s_1\) and of \(s_2\). (R2) and the take branch of (B): a cover that contains a copy of \(s\) is a nonempty selection of copies of \(s\) together with a cover of \(\mathcal U\setminus s\) by the other sets, and in (R2) every cover contains a copy of \(s\). The discard branch of (B): the covers without a copy of \(s\) are the covers by \(\mathcal S\setminus\{s\}\). (R3): every cover contains a copy of a set containing \(e_1\), which contains \(e_2\), so a set of copies covers \(\mathcal U\) if and only if it covers \(\mathcal U\setminus\{e_2\}\). (C): a set of copies that covers \(\mathcal U\setminus\{e\}\) either covers \(e\) or has no copy of a set containing \(e\), and the latter are the covers of \(\mathcal U\setminus\{e\}\) by \(\mathcal S\setminus N_I(e)\). (A): the dynamic program of (Nederlof, Rooij, and Dijk 2014 Proposition 27) handles each set with its polynomial when the set is processed, multiplying by \(P_s\) when it puts \(s\) into the solution; an empty set \(s\) contributes the factor \(1+P_s\) (any selection of its copies, in place of \((1+x)^{\operatorname{mult}(s)}\)), and an element of frequency \(0\) gives \(0\). Every polynomial that occurs is the generating function of selections of pairwise disjoint sets of vertices of \(G\) (products combine disjoint sets of copies), so its exponents lie in \(\{0,\dots,n\}\times\Sigma\), and every arithmetic operation on these polynomials takes time polynomial in \(n\) and \(|\Sigma|\). The measure, the recursion tree and the decompositions are those of the unweighted case, so the running time is again \(O(1.4815^n)\). This proves the weighted part of Theorem 13.1.
Nederlof, van Rooij and van Dijk state only Minimum Weight Dominating Set (Nederlof, Rooij, and Dijk 2014 Corollary 32), with a proof that refers to their polynomial-space algorithm, which has no merged sets; van Rooij’s thesis also states the counting version (Rooij 2011 Corollary 8.14).
The accompanying code checks this bookkeeping (not the running time) against brute force on small random graphs with true twins of different weights.
D.4 Remarks
Remark D.7 (variants). The following values come from the model of Appendix D.1 (recurrences and linear program), adapted to variants of the algorithm. Certified values are marked; the others are floating-point optima of the weights at \(\alpha=1.3\) (the objective \(\alpha^{v(7)+w(7)}\) does not depend on the scale of the weights).
With the previous list \(\mathcal X_{14}\) and \(\sigma=4\), the same proof gives \(O(1.4835^n)\) (certified: base \(<1.483408\), with \(L\approx0.378511246\) and \(30{,}988\) vectors). With the form \(\varphi_{\mathsf{S}}\) of Theorem 1.3 alone, the bases are \(1.4837\) (\(\mathcal X_{14}\)) and \(1.4818\) (\(\mathcal X_{30}\)).
The improvement comes from handing sets of size \(4\) to the dynamic program. With the previous \(\sigma=3\), the new width bounds do not lower the running-time bound (as noted after Proposition D.10); with the coefficients of Fomin, Gaspers, Saurabh and Stepanov (Fomin et al. 2009 Lemma 1), the switch at \(\sigma=4\) gives only \(1.5997^n\).
Other thresholds are worse: switching when sets have size at most \(3\) and elements frequency at most \(5\) gives \(1.4930^n\); sets at most \(4\) and elements at most \(5\), \(1.5117^n\); sets at most \(5\) and elements at most \(4\), \(1.5240^n\) (all without exceptional elements). With weights that are constant only from degree \(9\) on, the optimum for \(\mathcal A_{4,\mathcal X_{30}}\) is unchanged.
The list \(\mathcal X_{30}\) was found by a greedy search; we did not try to optimize it further.
Remark D.8 (status of the computations). The floating-point optimizer only produces candidate weights; every constant in the proofs of Proposition D.10 and Theorem 13.1 is certified as described there. A separate recheck, with code written apart from the main script, of all branching vectors up to degree \(12\) (\(1{,}747{,}700\) vectors) found the largest value \(0.99999961\) of \(\alpha^{-a}+\alpha^{-b}\), consistent with Lemma D.2.
D.5 A gap in the previous analysis
This subsection describes a gap in the previous running-time analysis of the algorithm of Nederlof, van Rooij and van Dijk for counting dominating sets (Nederlof, Rooij, and Dijk 2014), which also appears in van Rooij’s thesis (Rooij 2011, sec. 8.5). In the notation of Section 13, it is the algorithm \(\mathcal A_{3,\mathcal X_{14}}\), with switching threshold \(\sigma=3\) and the previous list \(\mathcal X_{14}\) of exceptional types (Section 13.1). The previous recurrences do not cover branchings on a set of size \(4\) that contains an element of frequency \(4\), and with the previous weights some of these cases violate the claimed branching factor (Proposition D.9). We show that the algorithm does branch on such sets, and that with all cases included it runs in time \(O(1.5004^n)\) (Proposition D.10). The analysis of Theorem 13.1 in Appendix D.2 uses the corrected set of recurrences.
Throughout, the notation is that of Section 13.1 and Appendix D.1: the measure \(k\) of (13.3) with weights \(v\) and \(w\) and their increments \(\Delta v\) and \(\Delta w\), the set vectors \(S_{d,r}\) and element vectors \(E_{d,r}\) of (D.2) and (D.1), the branching factor \(\tau(a,b)\), and the linear program for the pathwidth at the switch.
The previous analysis.
The thesis (Rooij 2011 Lemma 8.11, p. 152) and the journal version (Nederlof, Rooij, and Dijk 2014 Lemma 29, pp. 728–729) state that, with the previous weights of Table 12 ((Rooij 2011, 151), (Nederlof, Rooij, and Dijk 2014, 728)), the branching produces at most \(1.26089^{k-h}\) subproblems of measure \(h\), where \(k\) is the measure of the input instance. The linear program of (Rooij 2011 Lemma 8.12) and (Nederlof, Rooij, and Dijk 2014 Lemma 30) has value \(0.325782\), so that the dynamic program on a subproblem of measure \(h\) runs in time \(O(1.25334^{h})\). From these, (Rooij 2011 Theorem 8.13) and (Nederlof, Rooij, and Dijk 2014 Theorem 31) conclude the running time \(O(1.26089^{(0.749538+1)n})=O(1.5002^n)\).
We reproduced the previous analysis exactly, including the value \(0.325782\) of the linear program. With the previous weights, every branching vector of Lemma D.1 for \(\sigma=3\) has \(\tau\le1.260893\), except four set vectors \(S_{4,r}\) of degree \(4\), where \(r_i\) is the number of elements of the set that have frequency \(i\).
Proposition D.9 (the uncovered case). For \(\sigma=3\) and the previous weights, the set vector \(S_{4,r}\) with \(r_4=4\) is \[\bigl(w(4)+4\Delta v(4),\ w(4)+4v(4)+12\Delta w(4)\bigr)=(1.352437,\ 5.215817),\] and \(\tau(1.352437,5.215817)=1.27583>1.26089\). Also \(\tau>1.26089\) for the set vectors \(S_{4,r}\) with \((r_3,r_4)\) equal to \((3,1)\), \((2,2)\) or \((1,3)\).
Code: nrd_dominating_set.py
Proof. With the previous weights, \(\Delta v(4)=0.658484-0.551206=0.107278\) and \(\Delta w(4)=0.923325-0.785112=0.138213\), so the entries are \(0.923325+0.429112=1.352437\) and \(0.923325+2.633936+1.658556=5.215817\). The values of \(\tau\) were computed numerically by the accompanying code; \(\tau(1.352437,5.215817)\) lies in \((1.2758,1.2759)\), since \(1.2758^{-1.352437}+1.2758^{-5.215817}>1\) and \(1.2759^{-1.352437}+1.2759^{-5.215817}<1\). The largest value of \(\tau\) for the other three vectors is \(1.27004\). ∎
The algorithm branches on these sets.
The switch of (Rooij 2011 Algorithm 8.2) requires \(d(s)\le3\), so when \(d(s)=4\) and \(d(e)\le4\) the algorithm branches on the set (rule (B)), as the journal version says (Nederlof, Rooij, and Dijk 2014, 726–27). The case already occurs at the root for every cubic graph without true twins, where every set has size \(4\), every element has frequency \(4\) and no reduction rule applies. The coefficient \(12\,\Delta w(4)\) of the printed recurrence is the correct one, since no exceptional type in \(\mathcal X_{14}\) has a set of size \(5\).
A repair.
We do not know whether the algorithm is slower than \(O(1.5002^n)\); the gap concerns the proof. Including all cases of Lemma D.1 and re-optimizing the weights gives the following repair.
Proposition D.10 (the previous algorithm, repaired). The algorithm \(\mathcal A_{3,\mathcal X_{14}}\) of Nederlof, van Rooij and van Dijk, with the decompositions of (Fomin et al. 2009 Lemma 1), counts the dominating sets of each size of an \(n\)-vertex graph in time and space \(O(1.5004^n)\).
Code: nrd_dominating_set.py
Proof. We apply Lemma D.6 with \(\sigma=3\), \(\mathcal X=\mathcal X_{14}\) (which satisfies (13.1)), \(\alpha=\frac{13}{10}\), the repaired weights of Table 12, and \(\Psi=\{\varphi_\varepsilon\}\), and check its hypotheses.
The form. Let \(\varphi_{\mathrm{FGSS}}=(0,0,\frac16,\frac13,\frac{13}{30})\) be the coefficients of (Fomin et al. 2009 Lemma 1) for degrees \(1,\dots,5\), and let \(\varphi_\varepsilon=\varphi_{\mathrm{FGSS}}+\varepsilon\) on every degree, for a fixed \(\varepsilon>0\) chosen below. For fixed \(\varepsilon\), Lemma 1 of (Fomin et al. 2009) gives a path decomposition of width at most \(\sum_x\varphi_{\mathrm{FGSS}}(d_H(x))+\varepsilon|V(H)|+O(1)\) in polynomial time, so \(\varphi_\varepsilon\) is a computable form.
The branching vectors. The accompanying code checks (W1)–(W4) in exact rational arithmetic, and all \(31{,}003\) branching vectors of degree at most \(9\) in interval arithmetic (mpmath, 120-bit precision); the largest upper end of \(\alpha^{-a}+\alpha^{-b}\) is \(0.999999551\).
The linear program. The code also computes an exact rational solution of (D.8) for \(\{\varphi_{\mathrm{FGSS}}\}\), which certifies \(L(3,\mathcal X_{14},\{\varphi_{\mathrm{FGSS}}\})\le L\) with \(L\approx0.371341949\) and \(2^{L}<1.2935555<\alpha\). Every vertex counted in \(\Phi_\varphi\) has weight at least \(m_0=\min\{v(2),w(1)\}\) in (D.4), so \(\Phi_{\varphi_\varepsilon}\le\Phi_{\varphi_{\mathrm{FGSS}}}+\varepsilon/m_0\) on the polytope and \(L(3,\mathcal X_{14},\Psi)\le L+\varepsilon/m_0\). A fixed \(\varepsilon>0\) with \(2^{L+\varepsilon/m_0}<\alpha\) exists because \(2^L<1.2936<\alpha\).
The running time. Finally \(v(7)+w(7)=1.5462202\) and \(\alpha^{1.5462202}<1.500312\). ∎
The pathwidth bounds of this paper do not improve this running time. With the forms \(\varphi_{\mathsf{S}},\dots,\varphi_3\) listed before Lemma D.5 in place of \(\varphi_{\mathrm{FGSS}}\), the optimum for \(\sigma=3\) is still \(1.500312\) in floating point, because the dynamic program is not the bottleneck for \(\sigma=3\).
The source of the gap.
The case range of the previous recurrences appears to come from the polynomial-space analysis of the same authors (Rooij 2011 Theorem 8.5), (Nederlof, Rooij, and Dijk 2014 Theorem 11), where set branchings are needed only for elements of frequency at most \(d(s)-1\); re-optimizing the weights with that range reproduces the previous \(1.50016^n\) in floating point. The journal version has the same switching rule, weights and recurrences, so the gap is there too. Two printing slips, which also occur in the thesis (Rooij 2011), do not affect the results: constraints 2–4 on the weights (Nederlof, Rooij, and Dijk 2014, 728) are meant for \(i\ge1\), \(i\ge1\) and \(i\ge2\), and the subsumption rule (Nederlof, Rooij, and Dijk 2014 Algorithm 4, line 7) is printed with closed neighborhoods, \(N[e_1]\subseteq N[e_2]\), where (R3) uses open ones.