12 Further applications
The deterministic algorithm of Section 10 and Algorithm RS-\(\theta\) of Section 7 use the problem through two ingredients: an extension algorithm whose running time is \(O^{*}(2^{g(X)})\) for a computable running-time exponent \(g\), written with the shorthand \(g(X)=g(I,X,k)\) declared after Definition 3.2; and a pointwise affine bound \(g(X)\le\alpha-w(X)\) for the samples \(X\) of a solution \(S\), with a number \(\alpha\) and nonnegative integer weights \(w\colon S\to\mathbb Z_{\ge0}\) whose total \(w(S)\) is known (or, for RS-\(\theta\), the tree potential of Lemma 7.3). This section transfers them to four variants of Connected Dominating Set and then treats Directed Steiner Tree and Paired Domination (Sections 12.5 and 12.6). The four variants are distance-\(r\) domination (Section 12.1), vertex weights (Section 12.2), weak connectivity (Section 12.3) and directed graphs (Section 12.4). All algorithms use polynomial space. All four extension algorithms rest on the vertex-weighted directed Steiner lemma of Section 5.1 (Lemma 5.3): the first three through the directed Steiner encoding of Lemma 5.6, applied to states of red–blue graphs (Lemma D.11.1), and the directed variant through the extension algorithm for Directed Steiner Tree (Lemma 12.7). For each variant we state the problem and the results, and say what changes relative to Connected Dominating Set and why the analysis transfers; the lemmas and proofs are in Appendix D.11.
Directed Steiner Tree and Paired Domination share the feature of the earlier applications: the running time of the finishing step is exponential in a count that a sample can reduce, while a global constraint on the solution does not enter the exponent. In Directed Steiner Tree the count is the number of source components left by a sample, and the finishing step is inclusion–exclusion over them. In Paired Domination the count is the number of undominated vertices, and the global constraint, a perfect matching inside the solution, is handled by a Tutte matrix at no increase of the exponent. For both problems Algorithm MLS-\(\theta\) runs in polynomial space, with one-sided error, and below the best previous bound that we know (Table 2); the analysis is tight for Paired Domination (Proposition 12.11) and appears close to tight, numerically, for Directed Steiner Tree.
12.1 Connected \(r\)-domination
The two ingredients of Section 12 transfer to domination relations, which include distance-\(r\) domination.
Definition 12.1 (Domination relations). Let \(G\) be a graph. A domination relation on \(G\) assigns to every vertex \(v\) a set \(\mathcal{N}[v]\subseteq V\), the vertices that dominate \(v\), such that \(N[v]\subseteq\mathcal{N}[v]\) for every \(v\), and such that \(\mathcal{N}[v]\) can be computed from \(G\) (and the description of \(\mathcal{N}\)) in time polynomial in their total length. A set \(S\subseteq V\) is a connected \(\mathcal{N}\)-dominating set if it is nonempty, \(G[S]\) is connected, and \(\mathcal{N}[v]\cap S\neq\emptyset\) for every \(v\in V\); for a connected graph we write \(\gamma_{\mathrm{c}}^\mathcal{N}(G)\) for the minimum size of one. For \(X\subseteq V\) let \(\operatorname{und}_\mathcal{N}(X)=\{v\in V:\mathcal{N}[v]\cap X=\emptyset\}\) be the vertices not dominated by \(X\).
With \(\mathcal{N}[v]=N[v]\) this is connected domination. With \(\mathcal{N}[v]=\{u:\mathrm{dist}_G(u,v)\le r\}\) for an integer \(r\ge1\), which may be part of the input, it is connected \(r\)-domination, and Connected \(r\)-Dominating Set asks for \(\gamma_{\mathrm{c}}^\mathcal{N}(G)\). Every superset of an \(\mathcal{N}\)-dominating set is \(\mathcal{N}\)-dominating, so a connected \(\mathcal{N}\)-dominating set exists if \(G\) is connected (\(V\) itself is one), and for distance-\(r\) domination one exists only if \(G\) is connected. As in Section 5, \(G\) is connected and has \(n\ge2\) vertices.
What changes.
Both ingredients change, and each keeps its constants. First, the number of terminals \(|\mathrm{T}(J_X)|\) of (13) is replaced by \(g_\mathcal{N}(X)=|\operatorname{und}_\mathcal{N}(X)|+\operatorname{comp}(G[X])\), and the Steiner extension of Corollary 5.8 transfers with this running-time exponent (Lemma D.11.2): the completions of \(X\) are the solutions of a state (Definition 5.4) of a red–blue graph in which the red copy of \(v\) is joined to the blue copies of the vertices of \(\mathcal{N}[v]\), while connectivity is still measured by adjacency in \(G\) (Lemma D.11.1). Second, every vertex outside the solution is assigned to a solution vertex that dominates it, which need not be a neighbor, and this assignment is treated as a pendant edge of a virtual tree, the anchored tree, in which the solution is a connected dominating set. The running-time exponent of a sample is at most its number of terminals in the anchored tree (Lemma D.11.3), so the rate of Proposition 7.8 and the certificate (19), applied to the anchored tree, bound the exponential moments and the integer certificate for \(g_\mathcal{N}\) with the same constants as for connected domination, and the analyses of Theorems 7.2 and 10.4 transfer pointwise.
Theorem 12.2 (Connected \(\mathcal{N}\)-domination). Let \(\mathcal{N}\) be a domination relation. For connected \(n\)-vertex graphs \(G\), the value \(\gamma_{\mathrm{c}}^\mathcal{N}(G)\), in particular the minimum size of a connected \(r\)-dominating set for every \(r\ge1\) (with \(r\) part of the input), can be computed
(a) by a randomized algorithm with one-sided error in time \(O(1.7204^n)\) and polynomial space;
(b) deterministically in time \(O\bigl((\sqrt5-\frac12)^{n}\,2^{O(n(\log\log n)^{2}/\log n)}\bigr) =O(1.7361^n)\) and polynomial space.
The bases are those of Theorems 7.2 and 10.4. The proof is in Appendix D.11.2; Remark 12.6 lists what does not transfer.
12.2 Vertex-weighted connected domination and weighted MaxLeaf
In this subsection \(G\) is a connected graph with \(n\ge2\) vertices and \(\varphi\colon V\to\{0,1,\dots,\varphi_{\max}\}\) is a weight function; we write \(\varphi(X)=\sum_{x\in X}\varphi(x)\). To keep the notation of the paper, the weights are part of the instance in unary, so that the input length \(N\) is at least \(n+\varphi_{\max}\) and \(O^{*}\) hides factors polynomial in \(n+\varphi_{\max}\). Vertex-Weighted Connected Dominating Set asks for \(\gamma_{\mathrm{c}}^\varphi(G)=\min\{\varphi(S):S\text{ a connected dominating set of }G\}\), and Weighted Max Leaf Spanning Tree asks for the maximum of \(\varphi(\operatorname{leaves}(F))\) over the spanning trees \(F\) of \(G\), where \(\operatorname{leaves}(F)\) is the set of leaves of \(F\).
As in the unweighted case, for \(n\ge3\) the maximum leaf weight of a spanning tree equals \(\varphi(V)-\gamma_{\mathrm{c}}^\varphi(G)\) (Lemma D.11.4).
What changes.
The extension now has to find a completion of least weight. This is the minimum weight of a solution of the state \(J_X\) of (12), and the directed Steiner encoding of Lemma 5.6, which already allows weights on the blue vertices, computes it in time \(2^{|\mathrm{T}(J_X)|}(n+\varphi_{\max})^{O(1)}\) and polynomial space. So the running-time exponent is still \(|\mathrm{T}(J_X)|\), and it does not involve the weights. A completion of least weight may be large, so this extension does not control the number of added vertices; the moment and derandomized theorems need only two properties of the extension, which it has (Lemma D.11.5). The algorithms run the analyses of Theorems 7.2 and 10.4 for every weight budget and every solution size (Lemma D.11.6). The tree potential and the certificate (19) concern the solution and not its weight, so they hold unchanged; a minimum-weight solution itself has some size \(s^*\), at which the run for the optimal budget succeeds.
Theorem 12.3 (Vertex-weighted Connected Dominating Set and weighted MaxLeaf). For connected \(n\)-vertex graphs with vertex weights in \(\{0,\dots,\varphi_{\max}\}\), the minimum weight of a connected dominating set, and the maximum leaf weight of a spanning tree (by Lemma D.11.4 for \(n\ge3\); for \(n\le2\) it is \(0\) if \(n=1\) and \(\varphi(V)\) if \(n=2\)), can be computed
(a) by a randomized algorithm with one-sided error in time \(O(1.7204^n)(n+\varphi_{\max})^{O(1)}\) and polynomial space;
(b) deterministically in time \(\bigl(\sqrt5-\frac12\bigr)^{n}\,2^{O(n(\log\log n)^{2}/\log n)}(n+\varphi_{\max})^{O(1)} =O(1.7361^n)(n+\varphi_{\max})^{O(1)}\) and polynomial space.
The bases are those of Theorems 7.2 and 10.4. The proof is in Appendix D.11.3; Remark 12.6 lists what does not transfer.
12.3 Weakly connected domination
For a set \(S\subseteq V\) of a graph \(G\), the weakly induced subgraph \(\langle S\rangle_{\mathrm w}\) is the subgraph of \(G\) with vertex set \(N[S]\) whose edges are the edges of \(G\) with at least one end in \(S\); for a dominating set \(S\) it is a spanning subgraph. A weakly connected dominating set is a dominating set \(S\) for which \(\langle S\rangle_{\mathrm w}\) is connected; see (Dunbar et al. 1997). A graph has one if and only if it is connected (\(V\) is one), and every connected dominating set is one. Throughout, \(G\) is connected with \(n\ge2\) vertices, and \(\gamma_{\mathrm w}(G)\) is the minimum size of a weakly connected dominating set. For a set \(X\subseteq V\) write \(G^2[X]\) for the graph on \(X\) in which two vertices are adjacent when their distance in \(G\) is at most \(2\).
What changes.
Weak connectivity changes the running-time exponent. The number of terminals \(|\mathrm{T}(J_X)|=n-|N[X]|+\operatorname{comp}(G[X])\) is replaced by \[g_{\mathrm w}(X)=n-|N[X]|+\operatorname{comp}(G^2[X]),\] because a set is weakly connected dominating exactly when it is dominating and \(G^2[S]\) is connected (Lemma D.11.7); a red–blue graph whose blue copies are adjacent at distance at most \(2\) turns the completions of \(X\) into the solutions of a state, and Lemma D.11.1 gives an extension in time \(2^{g_{\mathrm w}(X)}n^{O(1)}\) and polynomial space (Lemma D.11.8). The pointwise certificate charges each edge of a spanning tree of \(\langle S\rangle_{\mathrm w}\) to an end in \(S\) (Lemma D.11.9); it has \(\alpha=n\) and total weight \(\Xi=n-1\) in place of \(\alpha=n-1\) and \(\Xi=n-2\), and the running time of the integer-affine algorithm is the same for both pairs (Lemma 10.2).
Theorem 12.4 (Weakly Connected Dominating Set). For connected \(n\)-vertex graphs, \(\gamma_{\mathrm w}(G)\) can be computed deterministically in time \(O\bigl((\sqrt5-\frac12)^{n}\,2^{O(n(\log\log n)^{2}/\log n)}\bigr)=O(1.7361^n)\) and polynomial space.
The bound rests on Lemma 10.1 and matches the deterministic bound for Connected Dominating Set (Theorem 10.4). The proof is in Appendix D.11.4; Remark 12.6 lists what does not transfer.
12.4 Directed Max Leaf Spanning Tree
Let \(\vec G\) be a digraph without loops or parallel arcs (opposite arcs are allowed) with \(n\ge2\) vertices. An out-branching rooted at \(r\) is a spanning subdigraph that is a tree in which every arc points away from \(r\); its leaves are its vertices of out-degree \(0\). Directed Max Leaf Spanning Tree asks for the maximum number of leaves of an out-branching. Binkele-Raible and Fernau (Binkele-Raible and Fernau 2012) solve it in time \(O^{*}(1.9044^n)\) and polynomial space, and in time \(O^{*}(1.8139^n)\) with exponential space. With the number \(k\) of leaves as the parameter, (Alon et al. 2009) decide in time \(2^{O(k\log^2k)}n^{O(1)}\) whether a strongly connected digraph has an out-branching with at least \(k\) leaves. For all digraphs, Kneis, Langer and Rossmanith (Kneis, Langer, and Rossmanith 2011) decide this in time \(4^kn^{O(1)}\), and (Daligault et al. 2010) in time \(3.72^kn^{O(1)}\), which also gives \(O(1.9973^n)\) for Directed Max Leaf Spanning Tree. (Binkele-Raible et al. 2012) give a kernel with \(O(k^3)\) vertices when the root is part of the input, and show that without the root there is no polynomial kernel unless \(\mathrm{coNP}\subseteq\mathrm{NP/poly}\).
For \(r\in V(\vec G)\), a set \(S\subseteq V(\vec G)\) is \(r\)-internal if \(r\in S\), every vertex of \(S\) is reachable from \(r\) in \(\vec G[S]\), and every \(v\notin S\) has an in-neighbor in \(S\).
By Lemma D.11.11, the maximum number of leaves of an out-branching is \(n-\min|S|\), the minimum over all roots \(r\) and all \(r\)-internal sets \(S\).
What changes.
For a fixed root \(r\), the role of the number of terminals is taken by \(g_r(X)=|\operatorname{und}_r(X)|+|\mathrm{Src}_r(X)|\), which counts the vertices outside \(X\cup\{r\}\) that have no in-neighbor in \(X\), and the source strong components of \(\vec G[X]\) that do not contain \(r\). The extension problem is an instance of Directed Steiner Tree on a digraph with a blue and a red copy of every vertex, and the extension algorithm of Lemma 12.7 solves it in time \(2^{g_r(X)}n^{O(1)}\) and polynomial space (Lemma D.11.12). The certificate is the directed form of the tree inequality: in an out-branching the weight \(d_F(u)-1\) of Lemma 5.10 becomes the number of children, minus \(1\) at the root, and with these weights the certificate (19) holds with the same constants \(\alpha=n-1\) and \(\Xi=n-2\) (Lemma D.11.13). So the algorithm of Theorem 10.4 applies for each root.
Theorem 12.5 (Directed Max Leaf Spanning Tree). For digraphs with \(n\) vertices, the maximum number of leaves of an out-branching (or the fact that there is none) can be computed deterministically in time \(O\bigl((\sqrt5-\frac12)^{n}\,2^{O(n(\log\log n)^{2}/\log n)}\bigr)=O(1.7361^n)\) and polynomial space.
The bound rests on Lemma 10.1. The proof is in Appendix D.11.5.
Remark 12.6 (What does not transfer). The closure sampling RSC of Section 8 is claimed for none of the four variants: its closure rule and its penalty for false candidates use the neighborhoods \(N(u)\) of vertices outside the sample, which an anchor at distance \(r\ge2\), a weight or an arc direction do not respect; we leave open whether a variant of the closure rule gives \(1.6991^n\) for Connected \(r\)-Dominating Set. The exponential-moment analysis of RS-\(\theta\) (Section 7) is claimed for \(\mathcal{N}\)-domination and for weights (Theorem 12.2(a) and Theorem 12.3(a)). For weak connectivity we do not expect it to beat the affine certificate of Lemma D.11.9: on spiders that certificate is an equality, and there the moment bound appears to decrease toward \(\sqrt5-\frac12\) (Proposition D.11.10 and the discussion after it). For out-branchings the tree potential of Lemma 7.3 does not apply, since it uses that a sampled vertex dominates its parent in the spanning tree of the solution, while in an out-branching a vertex dominates only its children. The equivalence with Max Leaf Spanning Tree (Lemma 5.1) is special to \(r=1\).
12.5 Directed Steiner Tree
An instance of Directed Steiner Tree is a digraph \(\vec G\) with \(n\) vertices, a root \(r\) and a set \(K\subseteq V(\vec G)\setminus\{r\}\) of terminals. Let \(U=V(\vec G)\setminus(\{r\}\cup K)\) be the set of non-terminals and \(n_U=|U|\). A set \(S\subseteq U\) is a Steiner set if every terminal is reachable from \(r\) in \(\vec G[\{r\}\cup K\cup S]\); the task is to find a Steiner set of least size. Two algorithms are immediate: inclusion–exclusion over the terminals (Lemma 5.3, with unit weights; see also (Misra et al. 2012) and (Jones et al. 2017 Lemma 3.5)) takes time \(2^{|K|}n^{O(1)}\), and enumeration takes time \(2^{n_U}n^{O(1)}\). Since \(|K|+n_U=n-1\), the better of the two runs in time \(2^{(n-1)/2}n^{O(1)}\), and we know of no better bound in terms of \(n\) for digraphs. Feldmann and Marx (Feldmann and Marx 2023) classify the directed Steiner network problems that are fixed-parameter tractable in the number of terminals. For undirected graphs and unit weights, (Fomin et al. 2013 Theorem 5) solve Steiner Tree in time \(O(1.3533^n)\) and polynomial space, which is below the bound of Theorem 12.8 on this special case; their branching uses a contraction lemma for adjacent terminals that is proved for undirected graphs.
The sampling algorithm works on rooted Steiner sets. Call \(S\subseteq U\) rooted if every vertex of \(K\cup S\) is reachable from \(r\) in \(\vec G[\{r\}\cup K\cup S]\), and let \(\Phi_{\mathrm{DST}}\) be the implicit set system with universe \(U\) whose solutions are the rooted Steiner sets. Every rooted set is a Steiner set, and the vertices of a Steiner set \(S\) that are reachable from \(r\) in \(\vec G[\{r\}\cup K\cup S]\) form a rooted Steiner set; so the least size of a solution of \(\Phi_{\mathrm{DST}}\) is the optimum. In particular, every inclusion-minimal Steiner set is rooted, so the restriction to rooted sets loses no minimum solution; it makes the running-time exponent of a sample, defined next, a count that can be read off the digraph.
The running-time exponent of a sample.
For \(X\subseteq U\) let \(\bar K_X=\{r\}\cup K\cup X\) and let \(\bar K^{r}_X\) be the set of vertices reachable from \(r\) in \(\vec G[\bar K_X]\). A source component of \(\vec G[\bar K_X\setminus \bar K^{r}_X]\) is a strong component that no arc of \(\vec G[\bar K_X\setminus \bar K^{r}_X]\) enters from outside. For the instance \(I=(\vec G,r,K)\), a set \(X\subseteq U\) and \(k\ge0\), let \(g(I,X,k)\) be the number of source components of \(\vec G[\bar K_X\setminus \bar K^{r}_X]\), and \(0\) if \(\bar K_X=\bar K^{r}_X\). It does not depend on \(k\), and for fixed \(I\) we write \(g(X)\), in agreement with the shorthand of Definition 3.2. Every vertex of \(\bar K_X\setminus \bar K^{r}_X\) is reachable within \(\vec G[\bar K_X\setminus \bar K^{r}_X]\) from some source component, since the condensation of a digraph is acyclic.
Lemma 12.7 (Extension). There is a deterministic algorithm that, given \((\vec G,r,K)\), a set \(X\subseteq U\) and weights \(w\colon U\to\{0,1,\dots,w_{\max}\}\), computes the least weight \(w(Y)\) over the sets \(Y\subseteq U\setminus X\) for which \(X\cup Y\) is a rooted Steiner set (\(\infty\) if there is none), in time \(2^{g(X)}(n+w_{\max})^{O(1)}\) and polynomial space. With unit weights it decides, for every integer \(k\ge0\), whether some \(Y\subseteq U\setminus X\) with \(|Y|\le k-|X|\) makes \(X\cup Y\) a rooted Steiner set, in time \(2^{g(X)}n^{O(1)}\). Moreover, \(g(X)\) is computable in polynomial time, so \(g\) is a running-time exponent for this algorithm for \(\Phi_{\mathrm{DST}}\)-Extension.
Proof. The set \(\bar K^{r}_X\), the strong components of \(\vec G[\bar K_X\setminus \bar K^{r}_X]\) and the arcs between them can be computed in polynomial time, and hence so can \(g(X)\). Choose one vertex in each source component of \(\vec G[\bar K_X\setminus \bar K^{r}_X]\), and let \(Q\) be the set of chosen vertices, so \(|Q|=g(X)\). Give every vertex of \(\bar K_X\) the weight \(0\) and every vertex \(v\in U\setminus X\) the weight \(w(v)\), and compute \(\operatorname{OPT}\), the least weight of a set \(D\subseteq V(\vec G)\setminus(\{r\}\cup Q)\) such that every vertex of \(Q\) is reachable from \(r\) in \(\vec G[\{r\}\cup Q\cup D]\), by Lemma 5.3 (root \(r\), terminals \(Q\), weights in \(\{0,\dots,w_{\max}\}\)). This takes time \(2^{g(X)}(n+w_{\max})^{O(1)}\) and polynomial space. We show that \(\operatorname{OPT}\) is the least \(w(Y)\) over the sets \(Y\) in question; with unit weights it is the least \(|Y|\), and one accepts if and only if \(\operatorname{OPT}\le k-|X|\).
Let \(X\cup Y\) be rooted, with \(Y\subseteq U\setminus X\). Then every vertex of \(\bar K_X\) is reachable from \(r\) in \(\vec G[\bar K_X\cup Y]\), and \(D=(\bar K_X\cup Y)\setminus(\{r\}\cup Q)\) is feasible, of weight \(w(Y)\). Conversely, let \(D\) be feasible, and put \(Y=D\cap(U\setminus X)\), so that \(w(Y)\) is the weight of \(D\) and \(\{r\}\cup Q\cup D\subseteq \bar K_X\cup Y\). In \(\vec G_Y=\vec G[\bar K_X\cup Y]\) every vertex of \(Q\) is reachable from \(r\). Each source component contains a vertex of \(Q\) and is strongly connected within \(\vec G[\bar K_X]\), so it is reachable in \(\vec G_Y\); every other vertex of \(\bar K_X\setminus \bar K^{r}_X\) is reachable from a source component within \(\vec G[\bar K_X\setminus \bar K^{r}_X]\); and \(\bar K^{r}_X\) is reachable by definition. So all of \(\bar K_X\) is reachable from \(r\) in \(\vec G_Y\). Let \(Y'\subseteq Y\) be the set of vertices of \(Y\) reachable from \(r\) in \(\vec G_Y\). A path from \(r\) in \(\vec G_Y\) visits only reachable vertices, so every vertex of \(\bar K_X\cup Y'\) is reachable from \(r\) in \(\vec G[\bar K_X\cup Y']\), that is, \(X\cup Y'\) is rooted, and \(w(Y')\le w(Y)\), as weights are nonnegative. ∎
The analysis.
The proof of the following theorem is in Appendix D.11.6. It fixes an inclusion-minimal rooted Steiner set \(S\) and an out-arborescence \(A\) of \(\vec G[\{r\}\cup K\cup S]\) rooted at \(r\), whose leaves other than \(r\) are terminals. The running-time exponent \(g(X)\) of a sample \(X\subseteq S\) is at most the number of trees of the forest \(A[\bar K_X]\) that do not contain \(r\) (Lemma D.11.14). Whether a vertex is counted depends only on whether it and its parent lie in \(\bar K_X\), so the resulting lower bound on the generating function is computed by a two-state recursion along \(A\) (Lemma D.11.15). As for RS-\(\theta\) (Lemma D.4.2), a region of the plane that the recursion maps into itself, up to known scale factors, bounds the generating function for all arborescences at once (Lemma D.11.16); three such regions, combined with rational weights, are checked by computer (Proposition D.11.17). The finishing step uses Lemma 5.3.
Theorem 12.8 (Directed Steiner Tree). Directed Steiner Tree on digraphs with \(n\) vertices can be solved by a randomized algorithm with one-sided error in time \(2^{0.457n}n^{O(1)}=O(1.3727^n)\) and polynomial space.
Lean, partial: dst_rates, dst_certs_exact, fa_dst_WS_minimum (formalisation)
Numerically, the analysis appears close to tight for this algorithm: on a family of digraphs built from a directed path with pendant terminals, the bound that the generating function gives is \(\Omega(1.3716^n)\), against the proved \(2^{0.457n}<1.3727^n\) (Appendix F.7).
Vertex weights.
With polynomially bounded integer weights on the non-terminals, the same algorithm computes the least weight of a Steiner set within the same time bound, up to a factor polynomial in \(w_{\max}\) (Corollary D.11.20, proved in Appendix D.11.8).
12.6 Paired Domination
Let \(G\) be a graph with \(n\) vertices and no isolated vertex. A paired dominating set is a dominating set \(S\) such that \(G[S]\) has a perfect matching, and \(\gamma_{\mathrm{pr}}(G)\) is the least size of one; it exists, as the vertex set of a maximal matching is one, since \(G\) has no isolated vertex. (Andreev et al. 2024) give an exact algorithm in time \(O(1.7159^n)\) and polynomial space; \(1.7159^n\) is also the bound of (Fomin et al. 2008) on the number of minimal dominating sets. We use the implicit set system \(\Phi_{\mathrm{PD}}\) with universe \(V\) whose solutions are the paired dominating sets, and for \(X\subseteq V\) we write \(\operatorname{und}(X)=V\setminus N[X]\) for the set of vertices that \(X\) leaves undominated.
The finishing step.
The undominated vertices are handled by inclusion–exclusion and the perfect matching by the Tutte matrix (Tutte 1947). Fix an orientation of the edges of \(G\), and let \(\mathbf T\) be the skew-symmetric \(V\times V\) matrix with \(\mathbf T_{uv}=x_e=-\mathbf T_{vu}\) for every edge \(e=uv\) oriented from \(u\) to \(v\), where the \(x_e\) are distinct indeterminates, and with all other entries \(0\). For \(A\subseteq V\) let \(\mathbf T_A\) be its principal submatrix on \(A\). Then \(\det\mathbf T_A=\mathrm{Pf}(\mathbf T_A)^2\), and the Pfaffian is \(\mathrm{Pf}(\mathbf T_A)=\sum_M\pm x_M\), summed over the perfect matchings \(M\) of \(G[A]\), where \(x_M=\prod_{e\in M}x_e\) and \(\mathrm{Pf}(\mathbf T_\emptyset)=1\). Distinct matchings give distinct monomials.
Lemma 12.9 (Tutte-matrix finishing). There is a randomized algorithm that, given \(G\), weights \(w\colon V\to\{0,\dots,w_{\max}\}\), a budget \(\varpi\ge0\), \(X\subseteq V\) and \(k\ge0\), never accepts if no \(Y\subseteq V\setminus X\) with \(|Y|\le k-|X|\) makes \(X\cup Y\) a paired dominating set of weight at most \(\varpi\), accepts with probability at least \(\frac12\) otherwise, and runs in time \(2^{|\operatorname{und}(X)|}(n+w_{\max})^{O(1)}\) and polynomial space for every outcome of its coins. With \(w\equiv0\) and \(\varpi=0\) this is an algorithm for \(\Phi_{\mathrm{PD}}\)-Extension with the same error bounds, in time \(2^{|\operatorname{und}(X)|}n^{O(1)}\).
So \(g(I,X,k)=|\operatorname{und}(X)|=n-|N[X]|\), for the instance \(I=G\) (with or without weights), is a running-time exponent, with integer values in \(\{0,\dots,n\}\), for a one-sided-error extension algorithm as in Corollary 3.15; it does not depend on \(k\), and we write \(g(X)\) as in Definition 3.2. It is the number of undominated vertices, the exponent of the inclusion–exclusion finishing step for Dominating Set: the perfect-matching requirement does not increase it.
The analysis.
The proofs of Lemma 12.9 and of the next two statements are in Appendix D.11.7. They fix a paired dominating set \(S\), a perfect matching \(M\) of \(G[S]\) and, for every vertex outside \(S\), an anchor in \(S\) among its neighbors. A sample \(X\subseteq S\) dominates a vertex outside \(S\) once it contains its anchor, and a vertex of \(S\) once it contains that vertex or its partner in \(M\); so the lower bound on the generating function that this gives factorizes over the pairs of \(M\) (Lemma D.11.18). A pair responsible for \(\bar n\) vertices, the pair itself and the vertices anchored at it, contributes at most \(\bar n\,h_{\bar n}(y)\) to \(\log\bigl((1+y)^n/W_S(y)\bigr)\), where for an integer \(\bar n\ge2\) \[h_{\bar n}(y)=\log(1+y)-\frac1{\bar n}\log\bigl(y^2+4\cdot2^{-\bar n/2}y+2^{-\bar n}\bigr).\] Let \(y^*=(3\sqrt3-1)/16=0.2622595\ldots\) and \(\psi_{\mathrm{pr}}=h_6(y^*)=0.7050097\ldots\). The worst pairs are responsible for six vertices (Lemma D.11.19), as is a pair \(uv\) with two vertices anchored at each of \(u\) and \(v\), as in a double star, and \(y^*\) is the minimizer of \(h_6\) (Proposition 12.11).
Theorem 12.10 (Paired Domination). For graphs \(G\) with \(n\) vertices and no isolated vertex, \(\gamma_{\mathrm{pr}}(G)\) can be computed by a randomized algorithm with one-sided error in time \(O(1.6302^n)\) and polynomial space.
Lean, partial: pd_constants, pd_star, pd_success (formalisation)
The only randomness in the extension algorithm of Lemma 12.9 is the identity test by the Schwartz–Zippel lemma. A deterministic version cannot rely on generic identity testing alone: Kabanets and Impagliazzo (Kabanets and Impagliazzo 2004) show that a deterministic polynomial-time identity test for polynomials given by arithmetic circuits would imply circuit lower bounds that are open.
We show next that this analysis of Algorithm MLS-\(\theta\) with the running-time exponent \(|\operatorname{und}(X)|\) is tight.
Proposition 12.11 (Tightness). The only critical point of \(h_6\) in \((0,\infty)\) is \(y^*\), and \(\min_{y\ge0}h_6(y)=h_6(y^*)\). Let \(G_L\) be the disjoint union of \(L\) double stars, each an edge \(uv\) with two pendant vertices at \(u\) and two at \(v\). Then the centers form the only paired dominating set \(S^*\) of \(G_L\) of size at most \(2L\), and if Algorithm MLS-\(\theta\) of Theorem 12.10 is run with a rate \(\psi'<\psi_{\mathrm{pr}}\), it accepts \(k=2L\) with probability tending to \(0\) as \(L\to\infty\).
Lean, partial: fa_pd_tight, pd_tight_crit, pd_tight_min, pd_tight_argmin, pd_tight_unique, Sstar_subset, pd_tight_W, pd_tight_ratio, pd_tight_W_le, pd_tight_moments, pd_tight_accepts, pd_tight_prob (formalisation)
So the base \(2^{\psi_{\mathrm{pr}}}=1.63015\ldots\) is exact for Algorithm MLS-\(\theta\) with the running-time exponent \(|\operatorname{und}(X)|\); a better bound needs a different running-time exponent or extension algorithm.
Vertex weights.
With vertex weights in \(\{0,\dots,w_{\max}\}\), written in unary, the least weight of a paired dominating set can be computed within the same time bound, up to a factor polynomial in \(w_{\max}\) (Theorem D.11.21, proved in Appendix D.11.8).