Appendix E Audit of the applications
This appendix collects, for each algorithmic theorem of the paper, what its proof imports, where its randomness comes from, how it treats weights, and what it outputs. Every algorithm in the tables runs in polynomial space, and every randomized one has one-sided error: it never outputs a value below the optimum, or never accepts a no-instance, and it succeeds with probability at least \(1-e^{-\kappa}\) for the confidence \(\kappa\) of the theorem, or at least \(1-1/e\) where the theorem says so.
Polynomial factors.
Every extension algorithm runs in time \(2^{g(I,X,k)}N^{O(1)}\) on every input, with one polynomial for all inputs (Definition 3.2); for randomized extension algorithms the bound holds for every outcome of the coins. The polynomial factor of Theorems 3.5 and 3.14 depends only on \(N\), since the rate, the loss factor and the confidence are at most \(N^{O(1)}\), and the trials of RSC run in time \(2^\theta r_0(n)\) for one polynomial \(r_0\) that does not depend on \(G\), \(s\), \(t\) or \(\theta\) (Lemma 8.4). The deterministic algorithms use Lemma 10.2, which holds uniformly for every implicit set system, extension algorithm and running-time exponent with values in \(\{0,\dots,n\}\), and they carry the further factor \(2^{O(n(\log\log n)^2/\log n)}\) of the balanced families. Weighted versions carry the factor \((n+w_{\max})^{O(1)}\) stated in their theorems, which is \(n^{O(1)}\) when \(w_{\max}\le n^{O(1)}\).
From decisions to optimal values.
The algorithms for Connected Dominating Set and its variants run the decision procedure for \(s=1,2,\dots\) and output the first accepted \(s\) (Lemma 5.2); vertex-weighted versions run it for every budget \(\varpi\) and output the least accepted budget (Lemma D.11.6). The randomized ones output a value that is never below the optimum and equals it with the success probability of their theorem; the deterministic ones output the optimal value. The algorithms for Connected Feedback Vertex Set, its weighted version, Connected Vertex Cover and Maximum-Weight Connected \(k\)-Subgraph also output a solution, which is optimal with probability at least \(1-1/e\) (at least \(1-e^{-\kappa}\) for Connected Vertex Cover), through the witness of the extension algorithm and, where the black box gives only a decision, a self-reduction (Lemma D.10.1). Graph Motif is a decision problem.
| Theorem | Extension step and imported results | Randomness | Weights |
|---|---|---|---|
| Theorems 6.4 and 7.2 | Steiner extension Corollary 5.8, from Lemma 5.3, proved in Appendix D.3; parameter: the number of terminals | uniform samples | none |
| Theorem 8.1 | the same, on the closed sample | uniform samples and the closure | none |
| Theorem 10.4 | the same | deterministic (balanced families, Theorem 9.6) | none |
| Theorem 12.2 | Lemma 5.3 on the red–blue graph with \(2n\) vertices (Lemma D.11.1) | (a) uniform samples; (b) deterministic | none |
| Theorem 12.3 | Lemma 5.3 with vertex weights, encoded as arc lengths (Appendix D.3) | (a) uniform samples; (b) deterministic | \(\{0,\dots,\varphi_{\max}\}\), unary |
| Theorem 12.4 | Lemma 5.3 via Lemma D.11.1 | deterministic | none |
| Theorem 12.5 | Lemma 12.7, from Lemma 5.3, once for every root | deterministic | none |
| Theorem | Extension step and imported results | Randomness | Weights |
|---|---|---|---|
| Theorem 11.8 | Cut & Count with forced vertices (Lemma 11.7), from the facts (CC1)–(CC3): Theorem A.13 of (Cygan et al. 2011), its proof, and the proof of Theorem 5.1 of (Cygan et al. 2022) (Appendix D.9.3) | uniform samples; Cut & Count | none |
| Theorem 11.17 | Lemma 11.7 as a modulator, the cut parity and weighted core evaluation (Lemmas D.10.8 and D.10.9), proved in Appendix D.10, and the isolation lemma (Cygan et al. 2022 Lemma 2.5) | uniform samples; Cut & Count; isolation | \(1\) to \(w_{\max}\le n^{O(1)}\); forced vertices weigh \(0\) |
| Theorem 11.13 | (Björklund, Kaski, and Kowalik 2016 Theorem 4 and Section 3.7) on the instance in which each component of the sample is contracted to a vertex with a fresh color (Lemma 11.11) | uniform samples; the black box | none |
| Theorem 11.15 | (Cygan 2012 Theorem 3), deterministic, on the contracted graph with pendant vertices (Lemma 11.14) | uniform samples only | \(1\) to \(w_{\max}\le n^{O(1)}\); contracted and pendant vertices weigh \(1\) |
| Theorem 11.16 | a weighted sieve adapted from (Björklund, Kaski, and Kowalik 2016), proved in Appendix D.10 | uniform samples; polynomial identity test | \(-w_{\max}\) to \(w_{\max}\le n^{O(1)}\); contracted vertices weigh \(0\) |
| Theorem | Extension step and imported results | Randomness | Weights |
|---|---|---|---|
| Theorem 12.8 | Lemma 12.7, from Lemma 5.3 | uniform samples | none |
| Corollary D.11.20 | the same with weights, and Lemma D.11.6 | uniform samples | \(\{0,\dots,w_{\max}\}\), unary |
| Theorem 12.10 | Lemma 12.9: Tutte matrix (Tutte 1947) and the identity test of Schwartz and Zippel (Schwartz 1980; Zippel 1979) | uniform samples; identity test | none |
| Theorem D.11.21 | the same with an indeterminate for the weights, and Lemma D.11.6 | uniform samples; identity test | \(\{0,\dots,w_{\max}\}\), unary |
Imported results.
The results that the proofs use as black boxes are: the Cut & Count facts (CC1)–(CC3) for Connected Feedback Vertex Set, which its weighted version uses only through the unweighted extension algorithm that supplies the modulator, together with the isolation lemma in the form of (Cygan et al. 2022 Lemma 2.5); the algorithm of Björklund, Kaski and Kowalik for Graph Motif; Cygan’s algorithm for weighted Connected Vertex Cover; and the Tutte matrix with the identity test of Schwartz and Zippel. The Steiner computations for connected domination and Directed Steiner Tree, the balanced families, the weighted counting for Connected Feedback Vertex Set (Lemmas D.10.8 and D.10.9), and the weighted sieve for Maximum-Weight Connected \(k\)-Subgraph are proved in this paper.