11 Component-count running times
This section treats problems whose solutions are vertex sets \(S\) of a graph \(G\) with \(G[S]\) connected, and whose extension algorithms run in time exponential in the number of components of the sample. Given a sample \(X\) of size \(t\) from a solution of size \(k\), with \(\operatorname{comp}(G[X])\) the number of components of \(G[X]\), the extension algorithm runs in time \[O^{*}\bigl(c^{\,k-t}\,2^{\operatorname{comp}(G[X])}\bigr),\] with \(c=3\) for Connected Feedback Vertex Set (a Cut & Count algorithm) and \(c=2\) for Graph Motif and Connected Vertex Cover (the algorithms of Björklund, Kaski and Kowalik and of Cygan). A sample of size \(t\) can have \(t\) components, so a running-time bound that depends on \(X\) only through \(t\) is the product-form bound \(c^{k-t}2^t\), for which multivariate Monotone Local Search (Corollary 4.6 with \((b,c,d)=(1,c,2)\)) gives the base \(3-2/c\ge2\) when \(c\ge2\), no better than enumeration. Our improvements come from the fact that a random part of a connected solution has few components once it is a sizeable fraction of the solution.
We use this fact through a lower bound on \(W_S(y)\) by a partition function of a spanning tree of the solution (Definition 11.1), which paths minimize up to a factor independent of \(k\) (Section 11.1). Section 11.2 turns this into the running time \(O^{*}(((4c-3)/(2c-1))^n)\) for Algorithm MLS-\(\theta\); the applications follow in Sections 11.3, 11.4 and 11.5.
Throughout, \(H\) is the binary entropy of Section 3.1, with the logarithm to base \(2\), and for a probability distribution \(\mathbb P\) on a finite set, \(H_e(\mathbb P)=-\sum_z\mathbb P(z)\ln\mathbb P(z)\) is its entropy with the natural logarithm. For a graph \(F\) and \(X\subseteq V(F)\) we write \(e(F[X])=|E(F[X])|\).
11.1 The partition function of a tree
Definition 11.1 (Tree partition function). For a tree \(F\) and a real \(\zeta\ge0\) let \[\mathcal Z_F(\zeta)=\sum_{X\subseteq V(F)}\zeta^{|X|}\,2^{e(F[X])},\] let \(M_\zeta=\bigl( \begin{smallmatrix}1&\zeta\\1&2\zeta \end{smallmatrix}\bigr)\), and let \(\lambda_{\max}(M_\zeta)\) be its largest eigenvalue, that is, \[\lambda_{\max}(M_\zeta)=\tfrac12\Bigl(1+2\zeta+\sqrt{(1+2\zeta)^2-4\zeta}\Bigr)=\tfrac12\Bigl(1+2\zeta+\sqrt{1+4\zeta^2}\Bigr).\] Both eigenvalues of \(M_\zeta\) are real and nonnegative, since the discriminant \(1+4\zeta^2\) is positive and their sum \(1+2\zeta\) and product \(\zeta\) are nonnegative. So \(\lambda_{\max}(M_\zeta)\) is also the largest absolute value of an eigenvalue of \(M_\zeta\), its spectral radius.
The function \(\zeta\mapsto\lambda_{\max}(M_\zeta)\) is continuous and increasing on \([0,\infty)\), with \(\lambda_{\max}(M_0)=1\), and \(\lambda_{\max}(M_\zeta)>1\) for \(\zeta>0\). Since \(\lambda_{\max}(M_\zeta)\) is the larger root of \(x^2-(1+2\zeta)x+\zeta\), it is at least half the trace: \(\lambda_{\max}(M_\zeta)\ge(1+2\zeta)/2\). On a path, \(M_\zeta\) is the transfer matrix of \(\mathcal Z_F(\zeta)\): the state of a vertex is \(1\) if it lies in \(X\) and \(0\) otherwise, a vertex in state \(1\) has weight \(\zeta\), and an edge between two vertices in state \(1\) has weight \(2\). The first lemma says that no tree on \(k\) vertices has a partition function smaller than \(\lambda_{\max}(M_\zeta)^{k-1}\), up to a factor depending only on \(\zeta\).
The quantity \(\mathcal Z_F(\zeta)\) is a weighted count of homomorphisms from \(F\) to a target with two vertices, \(0\) and \(1\), with vertex weights \(w_0=1\) and \(w_1=\zeta\) and the symmetric edge weights \(A=\bigl(\begin{smallmatrix}1&1\\1&2\end{smallmatrix}\bigr)\) (a loop of weight \(1\) at vertex \(0\), an edge of weight \(1\) between the two vertices, and a loop of weight \(2\) at vertex \(1\)), as in the proof below. For graphs without loops or weights, Csikvári and Lin (Csikvári and Lin 2014 Theorem 4.3) proved that every tree \(T\) with \(m\) vertices has \(\hom(T,G)\ge e^{\eta}\lambda^{m-1}\) homomorphisms into a connected graph \(G\), where \(\lambda\) is the largest adjacency eigenvalue of \(G\) and \(\eta\ge0\) is the natural-logarithm entropy of the probability vector formed by the squared entries of a unit Perron eigenvector. They proved it by running a stationary Markov chain on \(G\) down the tree, and the proof below follows theirs, with the vertex weights absorbed into a symmetric matrix. Whether the path minimizes such counts exactly depends on the target. Sidorenko (Sidorenko 1994) proved that among the trees with a given number of vertices the star has the most homomorphisms into every graph, whereas for some graphs some trees have fewer homomorphisms than the path (Galvin, McMillon, et al. 2025). Galvin, Marmorino, McMillon, Nir and Redlich (Galvin, Marmorino, et al. 2025) give criteria for paths to be the minimizers, for targets without edge weights (with weights on the vertices only); our target carries the weight \(2\) on a loop, and we know of no exact result for it. Our analysis needs only the bound up to the factor \(\min(1,\zeta)\).
Lemma 11.2 (Gibbs bound, after Csikvári and Lin). For every tree \(F\) with \(k\ge1\) vertices and every \(\zeta>0\), \[\mathcal Z_F(\zeta)\ \ge\ \min(1,\zeta)\,\lambda_{\max}(M_\zeta)^{k-1}.\]
Lean proof: cc_gibbs, Zpart_iso, spr_eigen, spr_facts, eIn_eq_induce (formalisation)
Proof. We write \(\mathcal Z_F(\zeta)\) as a sum of positive weights \(f(z)\) over labelings \(z\) of \(V(F)\), construct a probability distribution \(\mathbb P\) on the labelings from a reversible two-state Markov chain run down the tree, and apply the Gibbs inequality \(\ln \mathcal Z_F(\zeta)\ge\mathbb{E}_{\mathbb P}\ln f+H_e(\mathbb P)\); for this \(\mathbb P\) the right-hand side is \((k-1)\ln\lambda_{\max}(M_\zeta)\) up to a term depending only on \(\zeta\).
Write \(w_0=1\), \(w_1=\zeta\), \(A_{ij}=2\) if \(i=j=1\) and \(A_{ij}=1\) otherwise, for \(i,j\in\{0,1\}\). A subset \(X\) of \(V(F)\) is a labeling \(z\colon V(F)\to\{0,1\}\), and \(\mathcal Z_F(\zeta)=\sum_z f(z)\) with \[f(z)=\prod_{v\in V(F)}w_{z_v}\prod_{uv\in E(F)}A_{z_uz_v}>0 .\]
A reversible chain. Let \(\mathbf K_{ij}=\sqrt{w_i}\,A_{ij}\sqrt{w_j}\), that is, \(\mathbf K=\bigl( \begin{smallmatrix}1&\sqrt \zeta\\\sqrt \zeta&2\zeta \end{smallmatrix}\bigr)\). This is a symmetric matrix with the same characteristic polynomial \(x^2-(1+2\zeta)x+\zeta\) as \(M_\zeta\), so its largest eigenvalue is \(\lambda_{\max}(M_\zeta)\). The vector \((\sqrt \zeta,\lambda_{\max}(M_\zeta)-1)\) is an eigenvector for \(\lambda_{\max}(M_\zeta)\), by the first row of \(\mathbf K-\lambda_{\max}(M_\zeta)\,\mathrm{Id}\), with \(\mathrm{Id}\) the identity matrix, and both entries are positive, since \(\lambda_{\max}(M_\zeta)>1\). Let \(\mathbf v\) be this vector normalized to \(\mathbf v_0^2+\mathbf v_1^2=1\), and put \[\pi_i=\mathbf v_i^2,\qquad p_{ij}=\frac{\mathbf K_{ij}\mathbf v_j}{\lambda_{\max}(M_\zeta)\mathbf v_i}\qquad(i,j\in\{0,1\}).\] Then \(p_{ij}>0\) and \(\sum_jp_{ij}=(\mathbf K\mathbf v)_i/(\lambda_{\max}(M_\zeta)\mathbf v_i)=1\), so \((p_{ij})\) is a stochastic matrix. Moreover \(\pi_{ij}:=\pi_ip_{ij}=\mathbf v_i\mathbf K_{ij}\mathbf v_j/\lambda_{\max}(M_\zeta)\) is symmetric in \(i\) and \(j\), so \(\sum_i\pi_ip_{ij}=\sum_i\pi_jp_{ji}=\pi_j\): the probability vector \(\pi\) is stationary for \((p_{ij})\).
A labeling of the tree. Root \(F\) at a vertex \(r\). Let \(\mathbb P\) be the distribution of the random labeling that gives \(r\) a label drawn from \(\pi\) and then, going down the tree, gives every child \(v\) of a vertex \(u\) a label drawn from the row \(p_{z_u,\cdot}\), independently of everything else: \[\mathbb P(z)=\pi_{z_r}\prod_{u\to v}p_{z_uz_v}>0,\] the product over the \(k-1\) pairs of a parent \(u\) and a child \(v\). By stationarity and induction on the depth, every vertex has label distribution \(\pi\). Hence every edge, with parent \(u\) and child \(v\), has joint label distribution \(\Pr[z_u=i,z_v=j]=\pi_{ij}\), which is symmetric and has both marginals equal to \(\pi\).
The Gibbs inequality. For any probability distribution \(\mathbb P\) on the labelings, Jensen’s inequality for the concave function \(\ln\) gives \[\mathbb{E}_{\mathbb P}\ln f+H_e(\mathbb P)=\sum_{z:\,\mathbb P(z)>0}\mathbb P(z)\ln\frac{f(z)}{\mathbb P(z)} \le\ln\sum_{z}f(z)=\ln \mathcal Z_F(\zeta),\] where \(H_e(\mathbb P)=-\sum_z\mathbb P(z)\ln\mathbb P(z)\). We evaluate the left-hand side for our \(\mathbb P\). By the product form of \(\mathbb P\) and the marginals above, \[H_e(\mathbb P)=H_e(\pi)-(k-1)\sum_{i,j}\pi_{ij}\ln p_{ij},\qquad \mathbb{E}_{\mathbb P}\ln f=k\sum_i\pi_i\ln w_i+(k-1)\sum_{i,j}\pi_{ij}\ln A_{ij}.\] Since \(\ln A_{ij}=\ln \mathbf K_{ij}-\frac12\ln w_i-\frac12\ln w_j\) and both marginals of \((\pi_{ij})\) are \(\pi\), we have \(\sum\pi_{ij}\ln A_{ij}=\sum\pi_{ij}\ln \mathbf K_{ij}-\sum_i\pi_i\ln w_i\). Since \(\ln p_{ij}=\ln \mathbf K_{ij}+\ln\mathbf v_j-\ln\mathbf v_i-\ln\lambda_{\max}(M_\zeta)\) and \((\pi_{ij})\) is symmetric, the terms in \(\mathbf v\) cancel, and \(-\sum\pi_{ij}\ln p_{ij}=\ln\lambda_{\max}(M_\zeta)-\sum\pi_{ij}\ln \mathbf K_{ij}\). Adding up, the terms in \(\mathbf K\) cancel as well, and \[\ln \mathcal Z_F(\zeta)\ \ge\ \sum_i\pi_i\ln w_i+H_e(\pi)+(k-1)\ln\lambda_{\max}(M_\zeta) =\pi_1\ln \zeta+H_e(\pi)+(k-1)\ln\lambda_{\max}(M_\zeta) .\] Finally \(H_e(\pi)\ge0\) and \(\pi_1\in[0,1]\), so \(\pi_1\ln \zeta\ge\ln\min(1,\zeta)\). ∎
Paths attain the bound of Lemma 11.2 up to a factor depending only on \(\zeta\), by the next lemma. This is why the tightness results below (Proposition 11.9) use solutions whose tree is a path.
Lemma 11.3 (Paths). For a path \(F\) with \(k\ge1\) vertices and every \(\zeta\ge0\), \(\mathcal Z_F(\zeta)\le(1+\zeta)\,\lambda_{\max}(M_\zeta)^{k-1}\le2\lambda_{\max}(M_\zeta)^k\).
Lean proof: cc_path, cc_path_min (formalisation)
Proof. Let \(v_1,\dots,v_k\) be the vertices of the path in order, and \(\mathbf d=(1,\sqrt \zeta)\). With \(\mathbf K\) as in the proof of Lemma 11.2 (also for \(\zeta=0\)), each labeling \(z\) contributes \(\prod_vw_{z_v}\prod_{i<k}A_{z_{v_i}z_{v_{i+1}}}=\mathbf d_{z_{v_1}} \prod_{i<k}\mathbf K_{z_{v_i}z_{v_{i+1}}}\,\mathbf d_{z_{v_k}}\), because every inner vertex lies on two edges and each end on one. Hence \(\mathcal Z_F(\zeta)=\mathbf d^{\mathsf T}\mathbf K^{k-1}\mathbf d\). As \(\mathbf K\) is symmetric with eigenvalues in \([0,\lambda_{\max}(M_\zeta)]\) (their product is \(\zeta\ge0\) and their sum is positive), this is at most \(\|\mathbf d\|^2\lambda_{\max}(M_\zeta)^{k-1}=(1+\zeta)\lambda_{\max}(M_\zeta)^{k-1}\). Finally \(1+\zeta\le1+2\zeta\le2\lambda_{\max}(M_\zeta)\). ∎
11.2 Component-count running times and exponential-moment Monotone Local Search
We now state the property of a running-time exponent that the applications share, and the running time that Theorem 3.5 gives for it. Fix an implicit set system \(\Phi\) and an algorithm \(\mathcal{A}\) for \(\Phi\)-Extension with running-time exponent \(g\) (Definition 3.2); recall \(W_S(y)=\sum_{X\subseteq S}y^{|X|}2^{-g(I,X,k)}\) for a solution \(S\) of size \(k\) (Definition 3.3).
Definition 11.4 (Component-count bound). Let \(c\ge1\) and \(\gamma\ge0\) be constants. The running-time exponent \(g\) has a component-count bound with constants \((c,\gamma)\) if for every instance \(I\) and every solution \(S\in\mathcal{F}_I\) with \(|S|=k\ge1\) there is a tree \(F\) with vertex set \(S\) such that \[\tag{20} g(I,X,k)\ \le\ (k-|X|)\log c+|X|-e(F[X])+\gamma\qquad\text{for every }X\subseteq S .\]
The tree \(F\) is used only in the analysis. Typically the solutions induce connected subgraphs of a graph \(G\), the running-time exponent is \((k-|X|)\log c+\operatorname{comp}(G[X])\), and \(F\) is a spanning tree of \(G[S]\): then \(F[X]\) is a spanning forest of a subgraph of \(G[X]\), so \(\operatorname{comp}(G[X])\le\operatorname{comp}(F[X])=|X|-e(F[X])\), by the edge count for forests. For \(\sigma\in[0,1]\) and \(y\ge0\) put \[\tag{21} \phi_{c,\sigma}(y)=\log(1+y)-\sigma\log\frac{\lambda_{\max}(M_{cy/2})}{c}.\] For fixed \(y\) this is an affine function of \(\sigma\), so a bound on it over an interval of values of \(\sigma\) follows from its values at the two ends; the certificate of Section 11.4.2 uses this.
Corollary 11.5 (Generating function of a component-count running time). Let \(g\) have a component-count bound with constants \((c,\gamma)\), let \(S\in\mathcal{F}_I\) with \(|S|=k\ge1\), let \(F\) be a tree for \(S\) as in Definition 11.4, and put \(\sigma=k/n\).
(a) For every \(y>0\), with \(\zeta=cy/2\), \[W_S(y)\ \ge\ 2^{-\gamma}c^{-k}\mathcal Z_F(\zeta)\ \ge\ 2^{-\gamma}\,\frac{\min(1,\zeta)}{\lambda_{\max}(M_\zeta)} \Bigl(\frac{\lambda_{\max}(M_\zeta)}{c}\Bigr)^{k},\] and therefore \[\frac{(1+y)^n}{W_S(y)}\le2^\gamma\,\frac{\lambda_{\max}(M_\zeta)}{\min(1,\zeta)}\,2^{n\phi_{c,\sigma}(y)} .\]
(b) Put \(y^*=\frac{2(c-1)}{2c-1}\) and \(\zeta^*=cy^*/2=\frac{c(c-1)}{2c-1}\). Then \(\lambda_{\max}(M_{\zeta^*})=c\), and if \(c>1\), \[W_S(y^*)\ \ge\ 2^{-\gamma}\,\frac{\min(1,\zeta^*)}{c},\qquad \frac{(1+y^*)^n}{W_S(y^*)}\le\frac{2^\gamma c}{\min(1,\zeta^*)}\Bigl(\frac{4c-3}{2c-1}\Bigr)^n .\]
(c) \(W_S(0)=\mu_0(S)\ge2^{-\gamma}c^{-k}\) and \(\mu_k(S)\ge2^{-1-\gamma}\).
Lean, partial: cc_T_a, cc_T_a_of_hasCCBound, cc_T_a_of_gibbs, W_ge_Z (formalisation)
Proof. (a) By (20), each term of \(W_S(y)\) satisfies \(y^{|X|}2^{-g(I,X,k)}\ge2^{-\gamma}c^{-k}(cy/2)^{|X|}2^{e(F[X])}\). Summing over \(X\subseteq S\) gives the first inequality, and Lemma 11.2 the second. The last form follows by dividing \((1+y)^n\) by this bound and writing \((c/\lambda_{\max}(M_\zeta))^k=2^{-n\sigma\log(\lambda_{\max}(M_\zeta)/c)}\).
(b) The number \(c\) is a root of \(x^2-(1+2\zeta^*)x+\zeta^*\), because \(c^2-c-\zeta^*(2c-1)=c^2-c-c(c-1)=0\). The other root is \(\zeta^*/c=(c-1)/(2c-1)<c\), so \(\lambda_{\max}(M_{\zeta^*})=c\). Now (a) gives \(W_S(y^*)\ge2^{-\gamma}(\min(1,\zeta^*)/c)\cdot1^k\), and \(1+y^*=(4c-3)/(2c-1)\).
(c) For \(X=\emptyset\) the right-hand side of (20) is \(k\log c+\gamma\); for \(X=S\) it is \(k-(k-1)+\gamma=1+\gamma\), because \(F\) has \(k-1\) edges. ∎
Part (b) uses the same \(y^*\) for every solution size and, through Corollary 11.6 below, gives the closed-form base \((4c-3)/(2c-1)\), which is \(1.8\) for \(c=3\) and \(5/3\) for \(c=2\). Part (a) allows \(y\) to depend on \(\sigma\), and part (c) covers the two ends: no sampling (\(t=0\)) and enumeration (\(t=k\)). Together they give the following consequence of Theorem 3.5.
Corollary 11.6 (Algorithm MLS-\(\theta\) for component-count running times). Let \(\mathcal{A}\) solve \(\Phi\)-Extension, either deterministically with running-time exponent \(g\), or with one-sided error as in Corollary 3.15, and let \(g\) have a component-count bound with constants \((c,\gamma)\). Let \(\psi>0\) and \(\Gamma_0\ge1\) be constants such that every \(\sigma\in(0,1]\) satisfies at least one of
(R1) \(\sigma\log c\le\psi\);
(R2) \(H(\sigma)\le\psi\);
(R3) \(\phi_{c,\sigma}(y)\le\psi\) for some \(y>0\) with \(\lambda_{\max}(M_{cy/2})/\min(1,cy/2)\le\Gamma_0\).
Then for every \(k\ge1\), every instance \(I\) and every \(\kappa>0\) as in Theorem 3.5, Algorithm MLS-\(\theta\)\((\psi,\Gamma,\kappa)\) with \(\Gamma=2^{1+\gamma}\Gamma_0\), given \((I,k)\), runs in time \(2^{\psi n}N^{O(1)}\) and in space \(N^{O(1)}\) plus the space of \(\mathcal{A}\), answers no if \(\mathcal{F}_I\) contains no set of size at most \(k\), and answers yes with probability at least \(1-e^{-\kappa}\) if \(\mathcal{F}_I\) contains a set of size exactly \(k\). In particular this holds with \(\psi=\log((4c-3)/(2c-1))\) for every \(c>1\).
Proof. Items (i) and (ii) of Theorem 3.5 give the time, space and soundness; for a randomized \(\mathcal{A}\) use Corollary 3.15, which doubles \(\Gamma\) in the cap and in the trial counts. The rate \(\psi\) is irrational in general, for instance \(\psi=\log1.8\); the cap and the trial counts are then any integers in the ranges of (2), which are found in time \(N^{O(1)}\) from an approximation of \(\psi\) to within \(1/(4n)\). For item (iii), let \(S\in\mathcal{F}_I\) with \(|S|=k\) and \(\sigma=k/n\). If (R1) holds, then by Corollary 11.5(c) \(W_S(0)\ge2^{-\gamma}2^{-\sigma n\log c}\ge(1+0)^n2^{-\psi n}/\Gamma\). If (R2) holds, then \(\binom nk\le2^{nH(\sigma)}\le2^{\psi n}\), and Corollary 11.5(c) gives \(\mu_k(S)/\binom nk\ge2^{-1-\gamma}2^{-\psi n}\ge2^{-\psi n}/\Gamma\), which is (\(\star\)). If (R3) holds with \(y\), then Corollary 11.5(a) gives \((1+y)^n/W_S(y)\le2^\gamma\Gamma_02^{\psi n}\le\Gamma2^{\psi n}\). In the first and third case the condition \(W_S(y)\ge(1+y)^n2^{-\psi n}/\Gamma\) of Theorem 3.5 holds, with \(y=0\) in the first case, and it implies (\(\star\)). For the last claim, (R3) holds for every \(\sigma\) with \(y=y^*\) and \(\Gamma_0=c/\min(1,\zeta^*)\), by Corollary 11.5(b). ∎
The parameters of Corollary 11.6 have the following roles. The constant \(\psi\) is the rate: the target running time is \(2^{\psi n}\). Condition (R1) covers the solution fractions \(\sigma\) for which running \(\mathcal{A}\) without a sample (\(t=0\)) is fast enough, (R2) those for which enumerating \(k\)-subsets (\(t=k\)) is, and (R3) those for which the generating-function bound of Corollary 11.5(a) is. The constant \(\Gamma_0\) bounds the factor \(\lambda_{\max}(M_\zeta)/\min(1,\zeta)\) of that bound; together with the factor \(2^{1+\gamma}\) it enters only the loss factor \(\Gamma\) of condition (\(\star\)), not the rate. Real-valued running-time exponents are handled as in Remark 3.7. The decision problem is solved by running the algorithm for every \(k\) (Remark 3.6); membership of \(\emptyset\) in \(\mathcal{F}_I\) is tested directly.
The best rate for a given \(c\).
The best rate \(\psi\) that Corollary 11.6 can certify for a given \(c\), when \(y\) in (R3) may be chosen freely, is \[\psi_c=\max_{0\le\sigma\le1}\ \min\Bigl(\sigma\log c,\ H(\sigma),\ \inf_{y>0}\phi_{c,\sigma}(y)\Bigr).\] By Lemma 11.3, solutions whose tree \(F\) is a path with equality in (20) attain this rate up to polynomial factors by the argument of Proposition 11.9(a), which makes this precise for \(c=3\); and Lemma 11.2 shows that no other tree has a smaller partition function \(\mathcal Z_F(\zeta)\), up to a factor depending only on \(\zeta\). For \(c=3\) the closed form is optimal: \(\psi_3\le\log1.8\) by Corollary 11.5(b), and \(\psi_3\ge\log1.8\), since at \(\sigma=26/45\) the infimum equals \(\log1.8\) (Lemma D.9.8) and both \(\sigma\log3\) (by the proof of Lemma D.9.8) and \(H(\sigma)\) are larger: as \(1/2\le26/45<3/5\) and \(H\) decreases on \([1/2,1]\), \(H(\sigma)\ge H(\tfrac35)=\log5-\tfrac35\log3-\tfrac25>2\log3-\log5=\log1.8\), which is equivalent to \(5^{10}=9765625>6377292=4\cdot3^{13}\). For \(c=2\) it is not: the base \(5/3\) is larger than \(2^{\psi_2}\approx1.6443\), because at the solution fraction \(\sigma\) that attains the maximum in \(\psi_2\) the infimum over \(y\) is not attained at \(y^*\). The following table compares, for a few \(c\), three bases: the base \(\max_\sigma\min(c^\sigma,2^{H(\sigma)})\) obtained by running \(\mathcal{A}\) without a sample in time \(O^{*}(c^k)\) or enumerating all \(k\)-subsets, whichever is faster; the base given by the mean-exponent theorem (Theorem 4.1), for which the expected number of components of a uniformly random \(t\)-subset \(X\) of a connected \(k\)-set \(S\) is at most \(t-t(t-1)/k\) (each of the \(k-1\) edges of a spanning tree of \(G[S]\) lies in \(G[X]\) with probability \(t(t-1)/(k(k-1))\)); and \(2^{\psi_c}\). All entries are floating-point evaluations and are not used in any proof, except \(1.8\), which is exact; for \(c=2\), Lemma 11.12 certifies \(2^{\psi_2}\le1.6444\), and for \(c=4\) and \(c=6\) the entries in the column \(2^{\psi_c}\) agree to five decimals with the closed-form upper bounds \(13/7=1.857142\ldots\) and \(21/11=1.909090\ldots\) of Corollary 11.5(b).
| \(c\) | \(\max_\sigma\min(c^\sigma,2^{H(\sigma)})\) | mean exponent | \(2^{\psi_c}\) |
|---|---|---|---|
| \(2\) | \(1.70871\) | \(1.64877\) | \(1.64429\) |
| \(3\) | \(1.95258\) | \(1.80802\) | \(1.8\) |
| \(4\) | \(2\) | \(1.86182\) | \(1.85714\) |
| \(6\) | \(2\) | \(1.91121\) | \(1.90909\) |
11.3 Connected Feedback Vertex Set
A connected feedback vertex set of a graph \(G\) is a set \(S\subseteq V(G)\) such that \(G-S\) is a forest and \(G[S]\) is connected. We write \(\operatorname{OPT}(G)\) for the minimum size of a connected feedback vertex set of \(G\), if one exists; Connected Feedback Vertex Set asks, given \(G\), for one of size \(\operatorname{OPT}(G)\). We are not aware of a published exact algorithm for Connected Feedback Vertex Set that runs in time \(O((2-\varepsilon)^n)\) for a constant \(\varepsilon>0\). Without the connectivity constraint, (Fomin et al. 2008) find a minimum feedback vertex set in time \(O(1.7548^n)\) and show that a graph with \(n\) vertices has at most \(1.8638^n\) minimal feedback vertex sets. (Misra et al. 2012) gave the first fixed-parameter algorithm for Connected Feedback Vertex Set, in time \(c^kn^{O(1)}\) for a constant \(c\). (Cygan et al. 2022) solve the problem by a Monte Carlo algorithm in time \(3^kn^{O(1)}\) and polynomial space, where \(k\) is the solution size. For each \(k\), running this algorithm or enumerating all \(k\)-subsets, whichever is faster, gives time \(\max_{0\le\sigma\le1}\min(3^{\sigma},2^{H(\sigma)})^n n^{O(1)}\); a floating-point evaluation of the maximum gives the base \(1.9526\), at \(\sigma\approx0.6091\). This combination is folklore; we do not know of it in print, and it is the bound that we improve.
We sample \(X\), force it into the solution and complete it by a Cut & Count algorithm that, after contracting each component of \(G[X]\) to a forced vertex, runs in time \(3^{k-t}2^{\operatorname{comp}(G[X])}n^{O(1)}\) (Appendices D.9.2 and D.9.3 and Section 11.3.2), and Section 11.3.3 analyzes the sampling with the exponential moments.
11.3.1 Problem and the role of the sample
Graphs are finite and simple. We use the convention that the graph with no vertices is connected, so that \(\emptyset\) is a connected feedback vertex set of every forest. It suffices to treat connected graphs that are not forests. If \(G\) is a forest, then \(\operatorname{OPT}(G)=0\). If \(G\) is disconnected, a connected feedback vertex set lies inside one component of \(G\), so all other components must be forests; hence \(G\) has a connected feedback vertex set if and only if at most one component \(G_1\) of \(G\) contains a cycle, and then the connected feedback vertex sets of \(G\) that are nonempty are exactly those of \(G_1\). Both checks take polynomial time. For a connected graph \(G\), the set \(V(G)\) itself is a connected feedback vertex set, so \(\operatorname{OPT}(G)\) exists and is at most \(n\).
For a connected graph \(G\) that is not a forest, the connected feedback vertex sets form an implicit set system in the sense of Definition 3.1: the instance is \(G\), the universe is \(V(G)\) with \(n=|V(G)|\), and membership is decided by testing that \(G-S\) is acyclic and \(G[S]\) is connected. Every solution is nonempty. \(\Phi\)-Extension for this system (Definition 3.1), which we call Connected Feedback Vertex Set Extension, asks, given a connected graph \(G\), a set \(X\subseteq V(G)\) and an integer \(k\ge0\), whether some \(Y\subseteq V(G)\setminus X\) with \(|Y|\le k-|X|\) makes \(X\cup Y\) a connected feedback vertex set of \(G\).
Why the improvement needs a sample-dependent running-time exponent.
The following three facts show that the improvement does not come from classical or multivariate Monotone Local Search. First, the extension problem is not fixed-parameter tractable in the number \(k-|X|\) of further vertices under standard assumptions (Lemma D.9.1), so the theorem of (Fomin et al. 2019), which needs an extension algorithm with running time \(c^{k-|X|}N^{O(1)}\), does not apply. Second, the product-form running-time bound that our extension algorithm satisfies in the worst case \(\operatorname{comp}(G[X])=|X|\) is \(3^{k-|X|}2^{|X|}\), that is, \((b,c,d)=(1,3,2)\), and Corollary 4.6 turns it into \((1+2-2/3)^n=(7/3)^n\), worse than enumeration. Third, under the Set Cover Conjecture, no extension algorithm with a running-time bound \(c^{k-|X|}d^{|X|}N^{O(1)}\) gives a base below \(2\) through Corollary 4.6 (Proposition D.9.2). The running-time exponent we use instead is \[\tag{22} g(G,X,k)=(k-|X|)\log3+\operatorname{comp}(G[X]),\] which depends on \(X\) through the number of components of \(G[X]\). The proofs of the first and the third fact are in Appendix D.9 (Lemma D.9.1 and Proposition D.9.2).
11.3.2 The extension algorithm
The extension algorithm contracts each component of the sample to a forced vertex and then follows the iterative compression of (Cygan et al. 2011, 2022) along a sequence of edge contractions, with a Cut & Count test that keeps the forced vertices in the solution; its running time is exponential in the number of forced vertices, which is \(\operatorname{comp}(G[X])\). The construction and the proof of the following lemma are in Appendix D.9.
Lemma 11.7 (The extension algorithm). There is a randomized algorithm \(\mathcal{A}\) for Connected Feedback Vertex Set Extension that, given a connected graph \(G\) with \(n\) vertices, a set \(X\subseteq V(G)\) and an integer \(k\ge|X|\), runs in polynomial space and, for every outcome of its coins, in time \(3^{k-|X|}2^{\operatorname{comp}(G[X])}n^{O(1)}\). If it accepts, it outputs a set \(Y\subseteq V(G)\setminus X\) with \(|Y|\le k-|X|\) such that \(X\cup Y\) is a connected feedback vertex set of \(G\). On a yes-instance it accepts with probability at least \(3/4\). In particular, the running-time exponent (22) bounds its running time.
11.3.3 Exponential moments: the base \(1.8\)
We now run Algorithm MLS-\(\theta\) with the extension algorithm of Section 11.3.2 and analyze it through the exponential moments of the running-time exponent (22).
Theorem 11.8 (Connected Feedback Vertex Set). There is a randomized algorithm that, given a connected graph \(G\) with \(n\) vertices, outputs a connected feedback vertex set of \(G\) in time \(O^{*}(1.8^n)\) and polynomial space. The output always has size at least \(\operatorname{OPT}(G)\), and it has size exactly \(\operatorname{OPT}(G)\) with probability at least \(1-1/e\). For the running-time exponent (22), the rate \(\log1.8\) of Algorithm MLS-\(\theta\) cannot be lowered by a positive constant (Proposition 11.10).
Proof. If \(G\) is a forest, output \(\emptyset\). Otherwise the connected feedback vertex sets form an implicit set system whose solutions are nonempty (Section 11.3.1). The extension algorithm of Lemma 11.7 has one-sided error, accepts a yes-instance with probability at least \(3/4\), and runs in time \(2^{g(G,X,k)}n^{O(1)}\) for every outcome of its coins, with \(g(G,X,k)=(k-|X|)\log3+\operatorname{comp}(G[X])\) as in (22); comparisons of \(g\) with the thresholds of Algorithm MLS-\(\theta\) reduce to integer comparisons (Section 3.1). Every solution \(S\) induces a connected subgraph, so a spanning tree \(F\) of \(G[S]\) gives the component-count bound (20) with constants \((3,0)\). By Corollary 11.6 with \(c=3\), \(y^*=4/5\), \(\zeta^*=6/5\) and \(\psi=\log1.8\), Algorithm MLS-\(\theta\) with \(\kappa=1\), run for \(k=1,\dots,n\), returns a solution of size at most \(k\) only if one exists, and returns one with probability at least \(1-1/e\) for \(k=\operatorname{OPT}(G)\); each run takes time \(1.8^n\,n^{O(1)}\) and polynomial space. Output the smallest set found, and \(V(G)\), which is a connected feedback vertex set because \(G\) is connected, if none is found. Every output is a connected feedback vertex set, so its size is at least \(\operatorname{OPT}(G)\), and with probability at least \(1-1/e\) the run for \(k=\operatorname{OPT}(G)\) returns a set of size at most \(\operatorname{OPT}(G)\), which is then the output. ∎
By Corollary 11.5(b) with \(\gamma=0\), every solution satisfies \(W_S(4/5)\ge1/3\). The next proposition turns the path bound of Lemma 11.3 into an upper bound on the probability that a run of Algorithm MLS-\(\theta\) runs the extension algorithm on a subset of a solution \(S\) with \(|S|=26n/45\) whose running-time exponent is bounded below as for a path, for every run on \((I,k)\) with \(k\ge|S|\). Its proof, in Appendix D.9.5, uses that at the critical fraction \(\sigma^*=26/45\) the function \(\phi_{3,\sigma^*}\) of (21) has \(\inf_{y\ge0}\phi_{3,\sigma^*}(y)=\log1.8\), attained at \(y=4/5\) (Lemma D.9.8), and combines this with the necessity of (\(\star\)) (Proposition 3.10), in the form for budgets \(k\ge|S|\), and with the bound (4) on the moments \(\mu^{(k)}_t(S)\) of (3).
Proposition 11.9 (Tightness of \(1.8\)). Let \(I\) be an instance and \(S\in\mathcal{F}_I\) with \(|S|/n=26/45\). Suppose that \(g(I,X,k)\) is nondecreasing in \(k\) for every \(X\subseteq S\), and that, for a path \(F\) with vertex set \(S\) and a constant \(\gamma'\ge0\), \[g(I,X,|S|)\ \ge\ (|S|-|X|)\log3+|X|-e(F[X])-\gamma'\qquad\text{for every }X\subseteq S .\]
(a) The exponential moments of \(S\) (Definition 3.3, with \(k=|S|\)) satisfy \[\max_{0\le t\le|S|}\frac{\mu_t(S)}{\binom nt}\le2^{\gamma'+1}(n+1)(5/9)^n .\]
(b) For every integer \(k\) with \(|S|\le k\le n\), a run of Algorithm MLS-\(\theta\)\((\psi,\Gamma,\kappa)\) on \((I,k)\) runs \(\mathcal{A}\) on a subset of \(S\) with probability at most \(P_{\mathrm{nec}}\cdot2^{\gamma'+1}(n+1)\bigl(2^{\psi}\cdot5/9\bigr)^n\), with \(P_{\mathrm{nec}}\le N^{O(1)}\) as in Proposition 3.10.
(c) Suppose that \(\mathcal{A}\) never accepts a no-instance and that \(S\) is the only set in \(\mathcal{F}_I\) of size at most \(|S|\). Then a run on \((I,k)\) with \(k\le|S|\) answers yes, and a run on \((I,k)\) with any \(k\le n\) returns a solution of size at most \(|S|\), only if it runs \(\mathcal{A}\) on a subset of \(S\).
(d) Under the hypotheses of (c), let \(\varepsilon>0\) and \(\psi\le\log1.8-\varepsilon\), and run Algorithm MLS-\(\theta\)\((\psi,\Gamma,\kappa)\) on \((I,k)\) for \(k=1,\dots,n\), with any \(\Gamma\) and \(\kappa\) as in Theorem 3.5 (for a one-sided-error \(\mathcal{A}\), with \(2\Gamma\) as in Corollary 3.15). The probability that some run answers yes at a \(k\le|S|\), or that some run returns a set of size at most \(|S|\), is at most \(nP_{\mathrm{nec}}2^{\gamma'+1}(n+1)2^{-\varepsilon n}\), where \(P_{\mathrm{nec}}\le N^{O(1)}\) is the largest of the factors of Proposition 3.10 over these runs.
Families of instances that satisfy all hypotheses of Proposition 11.9 exist for Connected Feedback Vertex Set.
Proposition 11.10 (A tight family for Connected Feedback Vertex Set). Let \(\varepsilon>0\) be a constant. There is an infinite family of graphs on which the algorithm of the proof of Theorem 11.8, run with rates \(\psi\le\log1.8-\varepsilon\) in place of \(\log1.8\) and with any \(\Gamma\) and \(\kappa\) as in Theorem 3.5, outputs a minimum connected feedback vertex set with probability \(o(1)\) as the number \(n\) of vertices grows.
11.4 Graph Motif
The method of Section 11.3 needs a finishing step whose running time is exponential in the number of components of the sample, and a solution that is connected. Graph Motif has both, with a simpler finishing step: the randomized \(O^{*}(2^k)\) algorithm of Björklund, Kaski and Kowalik (Björklund, Kaski, and Kowalik 2016), used as a black box, after the components of the sample have been contracted and given fresh colors.
An instance of Graph Motif is a graph \(G\) with \(n\) vertices, a coloring \(\mathrm{col}:V(G)\to C\) and a multiset \(M\) over \(C\) with \(|M|=k\). A solution is a set \(S\subseteq V(G)\) such that \(G[S]\) is connected and \(\mathrm{col}(S)=M\) as multisets; every solution has size exactly \(k\). Björklund, Kaski and Kowalik (Björklund, Kaski, and Kowalik 2016) solve the problem in randomized time \(O^{*}(2^k)\) and polynomial space. They also show (Björklund, Kaski, and Kowalik 2016 Theorem 6) that if, for some constant \(\varepsilon>0\), the problem can be solved in time \(O((2-\varepsilon)^k)\), even only on instances in which every color occurs at most once in \(M\), then there is a constant \(\varepsilon'>0\) such that Set Cover on a universe of \(u\) elements can be solved in time \(O((2-\varepsilon')^u)\). (They state this for Maximum Graph Motif, which asks for a connected set \(S\) with \(|S|=k\) and \(\mathrm{col}(S)\subseteq M\); when \(|M|=k\), as in their reduction, this is the problem above.) Running their algorithm or enumerating all \(k\)-subsets, whichever is faster, gives \(\max_{0\le\sigma\le1}\min(2^{\sigma},2^{H(\sigma)})^n=(1.7087\ldots)^n\le1.7088^n\), at \(\sigma\approx0.7729\).
11.4.1 Finishing with forced vertices
The finishing step contracts each component of the sample to one vertex and gives that vertex a fresh color which the motif demands exactly once, so that the black-box algorithm must use every contracted component.
Lemma 11.11 (Extension). Given an instance \((G,\mathrm{col},M)\) with \(|M|=k\) and a set \(X\subseteq V(G)\) with \(|X|=t\le k\), a randomized algorithm can decide whether some solution \(S\) contains \(X\). It runs in time \(2^{(k-t)+\operatorname{comp}(G[X])}n^{O(1)}\) for every outcome of its coins and in polynomial space, never accepts if there is no such solution, and accepts with probability at least \(1/2\) if there is one.
Proof. If \(\mathrm{col}(X)\not\subseteq M\) as multisets, reject. Otherwise let \(X_1,\dots,X_q\) be the vertex sets of the components of \(G[X]\), \(q=\operatorname{comp}(G[X])\). Form \(G'\) from \(G\) by contracting each \(X_i\) into one vertex \(d_i\) (adjacent to every vertex outside \(X\) with a neighbor in \(X_i\); the vertices \(d_i\) are pairwise non-adjacent, since the \(X_i\) are components of \(G[X]\)), give \(d_i\) a fresh color \(c_i\), and let \(M'=(M\setminus\mathrm{col}(X))+\{c_1,\dots,c_q\}\), a multiset of size \(k-t+q\).
We claim that the solutions \(S\supseteq X\) of the original instance correspond to the connected sets \(S'\) of \(G'\) with \(\mathrm{col}(S')=M'\), by \(S\mapsto(S\setminus X)\cup\{d_1,\dots,d_q\}\). Such an \(S'\) contains every \(d_i\), because \(c_i\) occurs once in \(M'\) and only \(d_i\) has that color. Let \(S'\) be such a set. Then \(S=(S'\setminus\{d_1,\dots,d_q\})\cup X\) induces a connected subgraph of \(G\), since each vertex of the connected graph \(G'[S']\) expands to a connected set, and an edge of \(G'\) at a vertex \(d_i\) comes from an edge of \(G\) at \(X_i\). Its colors are \((M'-\{c_1,\dots,c_q\})+\mathrm{col}(X)=M\). Conversely, if \(S\supseteq X\) is a solution, the image of \(S\) in \(G'\) is connected and has the colors \(M'\).
If \(q\ge1\) and the vertices \(d_i\) do not all lie in one component of \(G'\), reject. Otherwise restrict \(G'\) to the component that contains the vertices \(d_i\) (to each component in turn if \(q=0\)), so that the host graph is connected. On this graph run the algorithm of Björklund, Kaski and Kowalik (Björklund, Kaski, and Kowalik 2016 Theorem 4 and Section 3.7) with motif \(M'\). It decides the existence of a connected induced subgraph \(S'\) with \(|S'|=|M'|\) and \(\mathrm{col}(S')\subseteq M'\) as multisets, that is, with \(\mathrm{col}(S')=M'\), in time \(2^{|M'|}n^{O(1)}\) and polynomial space; it never answers yes on a no-instance and answers yes on a yes-instance with probability at least \(1/2\). As \(|M'|=(k-t)+\operatorname{comp}(G[X])\), the lemma follows. ∎
11.4.2 Exponential moments: the base \(1.6444\)
For \(c=2\) the closed form of Corollary 11.5(b) gives the base \(5/3\), which is not optimal, so we optimize \(y\) for each solution fraction and certify the result. Since \(\phi_{2,\sigma}(y)\) is affine in \(\sigma\) for fixed \(y\), a finite list of intervals in \(\sigma\) suffices, and no rounding of a sample size has to be absorbed: \(y\) is a real parameter of the analysis only.
Lemma 11.12 (Rate certificate for \(c=2\)). Every \(\sigma\in(0,1]\) satisfies (R1), (R2) or (R3) of Corollary 11.6 with \(c=2\), \(\psi=0.71755\) and \(\Gamma_0=16\). Moreover \(0.71755<\log1.6444\), so \(2^{0.71755n}n^{O(1)}=O(1.6444^n)\).
Lean proof: cc_cert, spr_root (formalisation) · Certificates: component_count_rate_interval.py
Proof. Let \(\psi=0.71755\), \(\sigma_0=0.7175\) and \(\sigma_1=0.81\). The certificate of Appendix F.6 gives (o) \(\psi<\log1.6444\); (i) \(\sigma_0\le\psi\); (ii) \(H(\sigma_1)<\psi\) and \(\sigma_1\ge1/2\); (iii) for \(925\) consecutive intervals \([\sigma^-_j,\sigma^+_j]\) of width \(10^{-4}\) covering \([\sigma_0,\sigma_1]\), with explicit decimals \(y_j>0\), we have \(\max\bigl(\phi_{2,\sigma^-_j}(y_j),\phi_{2,\sigma^+_j}(y_j)\bigr)<\psi\) and \(\lambda_{\max}(M_{y_j})/\min(1,y_j)\le16\). If \(\sigma\le\sigma_0\), then (R1) holds, as \(\log c=1\). If \(\sigma\ge\sigma_1\), then (R2) holds, as \(H\) is decreasing on \([1/2,1]\). Otherwise \(\sigma\in[\sigma^-_j,\sigma^+_j]\) for some \(j\), and since \(\phi_{2,\sigma}(y_j)\) is affine in \(\sigma\), it is at most the maximum of its values at \(\sigma^-_j\) and \(\sigma^+_j\), so (R3) holds with \(y=y_j\). ∎
Theorem 11.13 (Graph Motif). Graph Motif can be solved by a randomized algorithm with one-sided error in time \(O(1.6444^n)\) and polynomial space.
The constant \(1.6444\) rests on Lemma 11.12; the algorithm of Björklund, Kaski and Kowalik (Björklund, Kaski, and Kowalik 2016) is used as a black box. The mean-exponent theorem (Theorem 4.1) with the same finishing step, run with the sample size that minimizes its bound, gives, by a numerical evaluation, a running time of \(O^{*}(1.6488^n)\) (the entry \(1.64877\) in the table of Section 11.2).
Proof. The solutions of an instance \((G,\mathrm{col},M)\) with \(|M|=k\) are the sets \(S\) with \(G[S]\) connected and \(\mathrm{col}(S)=M\); they have size \(k\ge1\) (for \(k=0\) the answer is trivial). By Lemma 11.11 the extension problem is solved with one-sided error, success probability at least \(1/2\) and polynomial space, in time \(2^{g(X)}n^{O(1)}\) for every outcome of the coins, with the integer running-time exponent \(g(X)=g(I,X,k)=(k-|X|)+\operatorname{comp}(G[X])\) (shorthand of Definition 3.2, for the instance \(I=(G,\mathrm{col},M)\)). A spanning tree of \(G[S]\) gives the component-count bound with constants \((2,0)\). Corollary 11.6 with Lemma 11.12, that is, with the rate \(\psi=0.71755\), gives running time \(2^{0.71755n}n^{O(1)}=O(1.6444^n)\); only the value \(k=|M|\) is run. ∎
Numerically, the base \(2^{\psi_2}\approx1.64429\) is attained at \(\sigma\approx0.71746\), where the running-time bound \(2^{\sigma n}\) of the plain algorithm equals the bound \(2^{n\phi_{2,\sigma}(y)}\) of (R3) with \(y\approx1.294\); the best strategy jumps there from no sampling to large samples. Lemma 11.12 proves the upper bound \(1.6444\); it is not sharp enough for the bound \(1.6443\). The analysis needs paths to minimize \(\mathcal Z_F\) up to a constant factor (Lemma 11.2). We do not know whether the exact inequality \(\mathcal Z_F\ge\mathcal Z_{\text{path}}\) holds for all trees on the same number of vertices.
11.5 Connected Vertex Cover and further applications
Each application below needs only a finishing step whose running-time exponent has a component-count bound; the sampling analysis is Corollary 11.6, with Lemma 11.12 for \(c=2\) and the closed form of Corollary 11.5(b) for \(c=3\). For optimization problems with weights we use the following standard reduction. If the weights are integers in \(\{-w_{\max},\dots,w_{\max}\}\) with \(w_{\max}\le n^{O(1)}\), we guess the optimal value \(\theta_w\) among \(O(nw_{\max})\) candidates and the size \(k\) of one optimal solution \(S^*\), and decide \(\Phi\)-Subset for the implicit set system \(\Phi\) whose solutions are the feasible sets of value at least (or at most) \(\theta_w\); its membership test is polynomial. The sampling analysis concerns only \(S^*\), and the weights never enter the running-time exponent.
11.5.1 Connected Vertex Cover, weighted and unweighted
A connected vertex cover of a graph \(G\) is a set \(S\subseteq V(G)\) such that \(G-S\) has no edges and \(G[S]\) is connected. In Weighted Connected Vertex Cover the vertices carry weights \(w\colon V(G)\to\{1,\dots,w_{\max}\}\), \(w_{\max}\le n^{O(1)}\), and we seek a connected vertex cover of minimum weight; unit weights give Connected Vertex Cover. We may assume that \(G\) is connected and has an edge: otherwise a connected vertex cover exists only if at most one component has an edge, and the other components can be discarded. The finishing step uses Cygan’s algorithm as a black box (Cygan 2012): given \(G\), positive integer weights bounded by a polynomial and an integer \(b\), it computes a minimum-weight connected vertex cover of size at most \(b\) (or reports that none exists), deterministically, in time \(2^bn^{O(1)}\) and polynomial space (his Theorem 3).
Lemma 11.14 (Finishing step). Given a connected graph \(G\) with at least one edge, weights as above, a set \(X\subseteq V(G)\) and integers \(k\ge|X|\) and \(\theta_w\), one can decide deterministically, in polynomial space and in time \(2^{k-|X|+\operatorname{comp}(G[X])}n^{O(1)}\), whether some \(Y\subseteq V(G)\setminus X\) with \(|Y|\le k-|X|\) makes \(X\cup Y\) a connected vertex cover of weight at most \(\theta_w\), and output such a \(Y\) if so.
Proof. Put \(k'=k-|X|\). If \(X=\emptyset\), run Cygan’s algorithm with \(b=k'\); accept if it returns a cover of weight at most \(\theta_w\), and output that cover as \(Y\). Otherwise let \(G_X\) be the contracted graph of Appendix D.9.2, with forced set \(\hat X=\{x_1,\dots,x_q\}\), \(q=\operatorname{comp}(G[X])\). For \(Y\subseteq V(G)\setminus X\), the set \(X\cup Y\) is a connected vertex cover of \(G\) if and only if \(\hat X\cup Y\) is one of \(G_X\): the proof of Lemma D.9.3(2) applies verbatim, because \(G-(X\cup Y)=G_X-(\hat X\cup Y)\), and a set is a vertex cover exactly when the graph without it has no edges. If \(G_X\) has one vertex, \(q=1\), \(Y=\emptyset\) is the only candidate, and the algorithm accepts if and only if \(w(X)\le\theta_w\), with output \(Y=\emptyset\). Otherwise \(G_X\) is connected with at least two vertices. Let \(G_X^+\) be \(G_X\) with a new pendant vertex \(r'\) attached to each \(r\in \hat X\), and give the vertices of \(\hat X\) and the new vertices weight \(1\).
Every connected vertex cover \(C\) of \(G_X^+\) contains \(\hat X\). Indeed, if \(r\in \hat X\setminus C\), then \(r'\in C\), to cover \(rr'\), and the other end \(u\) of an edge \(ru\) of \(G_X\) lies in \(C\); but the only neighbor of \(r'\) is \(r\notin C\), so \(G_X^+[C]\) is disconnected. Hence each \(r'\in C\) is a leaf of \(G_X^+[C]\), and removing all of them leaves a connected vertex cover of \(G_X\) that contains \(\hat X\), of no larger size and weight. Conversely, a connected vertex cover of \(G_X\) that contains \(\hat X\) is one of \(G_X^+\). So the minimum weight of a connected vertex cover of \(G_X^+\) of size at most \(k'+q\) equals the minimum of \(w(Y)+q\) over the sets \(Y\) with \(|Y|\le k'\) such that \(\hat X\cup Y\) is a connected vertex cover of \(G_X\). Compute it with Cygan’s algorithm, \(b=k'+q\), and accept if it is at most \(\theta_w-w(X)+q\). In that case the cover \(C\) returned by Cygan’s algorithm gives the output \(Y=C\setminus(\hat X\cup\{r':r\in\hat X\})\): by the above, \(\hat X\cup Y\) is a connected vertex cover of \(G_X\) with \(|Y|\le|C|-q\le k'\) and \(w(Y)\le w(C)-q\le\theta_w-w(X)\). ∎
Theorem 11.15 (Connected Vertex Cover). Let \(w_{\max}\le n^{O(1)}\) and let \(\kappa>0\) be a constant. There is a randomized algorithm that, given a connected graph \(G\) with \(n\ge2\) vertices and weights \(w\colon V(G)\to\{1,\dots,w_{\max}\}\), outputs a connected vertex cover of \(G\) in time \(O(1.6444^n)\) and polynomial space. On every outcome of its coins the output is a connected vertex cover of \(G\), so its weight is at least the minimum; with probability at least \(1-e^{-\kappa}\) its weight is the minimum. In particular, this holds for Connected Vertex Cover, and by the reduction above it extends to graphs that are not connected or have no edge.
The constant rests on Lemma 11.12; Cygan’s algorithm is used as a black box.
Proof. For each guess of \(\theta_w\in\{1,\dots,nw_{\max}\}\) and each \(k\in\{1,\dots,n\}\), run Algorithm MLS-\(\theta\) for the connected vertex covers of weight at most \(\theta_w\) and the size \(k\), and output the witness \(X\cup Y\) of an accepting run with the smallest \(\theta_w\). If no run accepts, output \(V(G)\), which is a connected vertex cover because \(G\) is connected. An accepting run returns a connected vertex cover of weight at most its \(\theta_w\) (Lemma 11.14), so on every outcome of the coins the output is a connected vertex cover. The extension problem for these implicit set systems is solved by Lemma 11.14, with running-time exponent \(g(G,X,k)=k-|X|+\operatorname{comp}(G[X])\), deterministically. Every solution induces a connected subgraph, so a spanning tree of \(G[S]\) gives the component-count bound with constants \((2,0)\), and Corollary 11.6 with Lemma 11.12 applies for every \(k\), with the rate \(\psi=0.71755\); there are polynomially many runs, each in time \(2^{0.71755n}n^{O(1)}\), which is \(O(1.6444^n)\) in total by Lemma 11.12. A run for the optimal \(\theta_w\) and \(k=|S^*|\) succeeds with probability at least \(1-e^{-\kappa}\), and no run accepts a value below the optimum. ∎
Comparison with published bounds.
For Connected Vertex Cover the best published bound in terms of \(n\) is \(O(1.7088^n)\) (Golovach, Heggernes, and Kratsch 2018 Corollary 1), from Cygan’s \(2^k\) algorithm and enumeration. For the weighted problem, enumerating the minimal connected vertex covers gives \(O^{*}(1.8668^n)\) (Golovach, Heggernes, and Kratsch 2018 Theorem 3) (with positive weights a minimum-weight connected vertex cover is minimal), and balancing Cygan’s Theorem 3 (Cygan 2012) against enumeration gives \(O(1.7088^n)\), a combination we have not seen stated. Our algorithm is randomized through the sampling only; the finishing step is deterministic.
11.5.2 Maximum-Weight Connected \(k\)-Subgraph
Given a graph \(G\), integer vertex weights \(w\colon V(G)\to\{-w_{\max},\dots,w_{\max}\}\) with \(w_{\max}\ge1\) and an integer \(1\le k\le n\), Maximum-Weight Connected \(k\)-Subgraph asks for a set \(S\) with \(|S|=k\) and \(G[S]\) connected that maximizes \(w(S)\); we call the sets \(S\) with \(|S|=k\) and \(G[S]\) connected, of any weight, connected \(k\)-sets. We know of no exact bound in terms of \(n\) besides enumeration of all \(k\)-sets; for the version without the size constraint, Buchanan, Wang and Butenko (Buchanan, Wang, and Butenko 2018) give \(O(1.5875^n)\). The finishing step below with \(X=\emptyset\) runs in time \(2^k(nw_{\max})^{O(1)}\); balanced against enumeration it gives \(O(1.7088^n)\) for \(w_{\max}\le n^{O(1)}\), the same base as for Graph Motif, and this folklore combination is the bound we compare with.
The finishing step.
As for Graph Motif (Lemma 11.11), the components \(X_1,\dots,X_q\) of the sample are contracted to vertices \(d_1,\dots,d_q\) of weight \(0\), and each new vertex receives a fresh color that must occur exactly once, while all other vertices share one color of multiplicity \(k-|X|\). The connected \(k\)-sets \(S\supseteq X\) then correspond to the connected sets of size \(k-|X|+q\) of the contracted graph that contain all vertices \(d_i\), with \(w(S)=w(X)\) plus the weight of the corresponding set. We detect these sets with the algebraic sieve of Björklund, Kaski and Kowalik (Björklund, Kaski, and Kowalik 2016), to which we add one indeterminate whose exponent records the weight of the set, and we recover the polynomial in this indeterminate by interpolation. Their cost-constrained lemma lets the coloring vary, so we derive the variant with a fixed coloring and a cost on each vertex from their proofs. A witness is found by deleting vertices one at a time. The finishing step takes time \(2^{(k-|X|)+\operatorname{comp}(G[X])} (nw_{\max})^{O(1)}\) and polynomial space and has one-sided error.
Theorem 11.16 (Maximum-Weight Connected \(k\)-Subgraph). Let \(1\le w_{\max}\le n^{O(1)}\). There is a randomized algorithm that, given a graph \(G\) with \(n\) vertices, weights \(w\colon V(G)\to\{-w_{\max},\dots,w_{\max}\}\) and an integer \(1\le k\le n\), either reports correctly that \(G\) has no connected \(k\)-set or outputs a connected \(k\)-set, in time \(O(1.6444^n)\) and polynomial space. The output has maximum weight with probability at least \(1-1/e\). In particular, the decision version (“is there a connected \(k\)-set of weight at least \(\theta\)?”) is solved with one-sided error.
The constant rests on Lemma 11.12. The proof is in Appendix D.10. The variant without the size constraint is not improved by this method.
11.5.3 Vertex-weighted Connected Feedback Vertex Set
In the vertex-weighted version of Connected Feedback Vertex Set the vertices carry weights \(w\colon V(G)\to\{1,\dots,w_{\max}\}\), and we seek a connected feedback vertex set of minimum weight. We know of no published algorithm in time \(O((2-\varepsilon)^n)\) for a constant \(\varepsilon>0\); the Cut & Count algorithm of (Cygan et al. 2022) is stated for the cardinality version.
The extension algorithm.
After contracting the sample (Lemma D.9.3(2)) and giving the forced vertices weight \(0\), the weight of a completion is \(w(X)\) plus the weight of its non-forced part. The weighted extension algorithm first runs the unweighted extension algorithm of Lemma 11.7, only to obtain a connected feedback vertex set of small excess, which serves as a structured modulator; so the intermediate graphs of the iterative compression never need weights. It then counts the objects of (CC1), through the proved Lemmas D.10.8 and D.10.9 rather than the cited dynamic program, with a weight function that adds to each isolating weight of a forest vertex a large multiple of its vertex weight, so that the weight of a counted candidate determines both its isolating weight and its vertex weight, and it finds a solution by self-reduction. It has the running-time exponent (22) of the unweighted algorithm. The two properties of the counting that it needs are proved in Appendix D.10.2, so they are not imported. They are a parity identity for the counted cuts (Lemma D.10.8) and a dynamic program over the forest outside the modulator (Lemma D.10.9). That program has four states per vertex for every weight function, and the weights change only the range of its weight index.
Theorem 11.17 (Vertex-weighted Connected Feedback Vertex Set). Let \(w_{\max}\le n^{O(1)}\). There is a randomized algorithm that, given a graph \(G\) with \(n\) vertices and weights \(w\colon V(G)\to\{1,\dots,w_{\max}\}\), reports correctly that \(G\) has no connected feedback vertex set or outputs one, in time \(O^{*}(1.8^n)\) and polynomial space. The output has minimum weight with probability at least \(1-1/e\). In particular, the decision version (“is there a connected feedback vertex set of weight at most \(\theta\)?”) is solved with one-sided error.
The proof is in Appendix D.10.