14 Connectivity problems
Many problems with a global connectivity or acyclicity constraint can be solved in time single exponential in the width of a given decomposition, and several of them are NP-hard on graphs of maximum degree \(3\) or \(4\). This section runs such algorithms on the decompositions of Theorem 1.5 and on the orderings of Corollary 10.2 and Theorem 3.6. This gives new running-time bounds for these problems on graphs of maximum degree \(3\) to \(6\), on graphs with a given number of edges, and for three parameterized problems (Theorem 14.1 and the paragraph on Almost Forest Deletion at the end of this section).
The algorithms that we use are the following. The Cut&Count technique of Cygan, Nederlof, Pilipczuk, Pilipczuk, van Rooij and Wojtaszczyk gives Monte Carlo algorithms in time \(c^{\mathop{\mathrm{tw}}}n^{O(1)}\) for a given tree decomposition of width \(\mathop{\mathrm{tw}}\) (Cygan et al. 2011 Theorem 1.2). The base is \(c=3\) for Feedback Vertex Set, Connected Vertex Cover and Steiner Tree, \(c=4\) for Connected Dominating Set and eight further problems on undirected graphs, and \(c=6\) for the directed versions of Min Cycle Cover, Longest Path and Longest Cycle and for Exact \(k\)-Leaf Outbranching. Cygan, Kratsch and Nederlof decide Hamiltonicity by a Monte Carlo algorithm in time \((2+\sqrt2)^{\mathop{\mathrm{pw}}}n^{O(1)}\) for a given path decomposition of width \(\mathop{\mathrm{pw}}\) (Cygan, Kratsch, and Nederlof 2012 Theorem 4.3), and Longest Path in the same time (Cygan, Kratsch, and Nederlof 2012 Theorem 4.6, stated with a proof sketch). The rank-based approach of Bodlaender, Cygan, Kratsch and Nederlof gives deterministic algorithms, for instance in time \((2+2^{\omega/2})^{\mathop{\mathrm{pw}}}n^{O(1)}\) for the traveling salesperson problem with nonnegative integer edge weights, where \(\omega\) is the matrix multiplication exponent (Bodlaender et al. 2015 Theorem 3.18). Bojikian, Chekan, Hegerfeld and Kratsch (Bojikian et al. 2022) and Bojikian, Chekan and Kratsch (Bojikian, Chekan, and Kratsch 2025) give algorithms of the same kind for a given linear ordering of cutwidth \(\operatorname{ctw}\), with smaller bases.
Combined with the pathwidth bound \(\frac n6\) of Fomin and Høie (Fomin and Høie 2006) and the per-degree bounds of Fomin, Gaspers, Saurabh and Stepanov (Fomin et al. 2009) (\(\frac n3\) for maximum degree \(4\) and \(\frac{13n}{30}\) for maximum degree \(5\)), these algorithms gave the fastest algorithms known to us for several of these problems on graphs of maximum degree \(3\), \(4\) and \(5\). Cygan et al. list the Cut&Count bounds (Cygan et al. 2011 Corollary 1.9). Cygan, Kratsch and Nederlof (Cygan, Kratsch, and Nederlof 2012 Corollary 4.5) state theirs for maximum degree \(3\), and Bodlaender et al. (Bodlaender et al. 2015 Corollary 3.19) theirs for cubic graphs. Kowalik and Majewski tabulate those for Hamiltonicity and the traveling salesperson problem (Kowalik and Majewski 2020 Table 1). The pathwidth bound of Fomin, Gaspers, Saurabh and Stepanov in terms of the numbers of vertices of each degree also bounds the width of the instances that remain after branching in parameterized algorithms for Co-Path Packing (Liu and Xiao 2026) and \(k\)-Co-Path Set (Sullivan and Poel 2016). With the bounds of Part I we obtain the following.
Theorem 14.1 (connectivity problems). Polynomial factors are omitted, all algorithms use exponential space, and the Monte Carlo algorithms have one-sided error at most \(\frac12\).
(a) Feedback Vertex Set and Connected Vertex Cover can be solved by Monte Carlo algorithms in time \(2^{m/6+o(n)}\le2^{n/3+o(n)}=O(1.2600^n)\) on graphs with \(m\) edges and maximum degree \(4\), and in time \(2^{\gamma_5m+o(n)}=O(1.4262^n)\) on graphs of maximum degree \(5\), where \(\gamma_5<0.20484\) is the constant of Theorem 3.6. Steiner Tree with unit weights can be solved by Monte Carlo algorithms in time \(3^{c_{3}n+o(n)}=O(1.1661^n)\) and \(3^{F_4n+o(n)}=O(1.3100^n)\) on graphs of maximum degree \(3\) and \(4\). Feedback Vertex Set can be solved on graphs of maximum degree \(6\) by a Monte Carlo algorithm in time \(3^{7n/16+o(n)}=O(1.6172^n)\). Feedback Vertex Set can be solved on graphs of maximum degree \(4\) deterministically in time \(5^{F_4n+o(n)}=O(1.4853^n)\).
(b) Connected Dominating Set, Connected Feedback Vertex Set, Connected Odd Cycle Transversal, Exact \(k\)-Leaf Spanning Tree (in particular Minimum and Maximum Leaf Spanning Tree), Maximum Full Degree Spanning Tree, Graph Metric Traveling Salesperson, and the undirected versions of Min Cycle Cover and Longest Cycle can be solved by Monte Carlo algorithms in time \(4^{c_{3}n+o(n)}=O(1.2139^n)\), \(4^{F_4n+o(n)}=O(1.4060^n)\) and \(4^{11n/32+o(n)}=O(1.6105^n)\) on graphs of maximum degree \(3\), \(4\) and \(5\). Minimum Leaf Spanning Tree (equivalently, Maximum Internal Spanning Tree) can be solved on graphs of maximum degree \(6\) by a Monte Carlo algorithm in time \(4^{7n/16+o(n)}=O(1.8341^n)\), and Connected Dominating Set on graphs of maximum degree \(3\) by a Monte Carlo algorithm in time \(3^{c_{3}n+o(n)}=O(1.1661^n)\). Maximum Leaf Spanning Tree has the bounds of Connected Dominating Set.
(c) Hamiltonian Cycle can be solved by Monte Carlo algorithms in time \((1+\sqrt2)^{c_{3}n+o(n)}=O(1.1312^n)\) on graphs of maximum degree \(3\), in time \((1+\sqrt2)^{m/6+o(n)}\le(1+\sqrt2)^{n/3+o(n)}=O(1.3416^n)\) on graphs with \(m\) edges and maximum degree \(4\), and in time \((2+\sqrt2)^{11n/32+o(n)}=O(1.5252^n)\) on graphs of maximum degree \(5\). Undirected Longest Path can be solved by Monte Carlo algorithms in time \((2+\sqrt2)^{c_{3}n+o(n)}=O(1.1874^n)\), \((2+\sqrt2)^{F_4n+o(n)}=O(1.3523^n)\) and \((2+\sqrt2)^{11n/32+o(n)}=O(1.5252^n)\) on graphs of maximum degree \(3\), \(4\) and \(5\).
(d) With \(\omega\le\frac94\) (OpenAI 2026; Amanov, Berg, and Zuiddam 2026), the traveling salesperson problem with nonnegative integer edge weights can be solved deterministically in time \((1+2^{\omega/2})^{c_{3}n+o(n)}=O(1.1757^n)\) on graphs of maximum degree \(3\), and in time \((2+2^{\omega/2})^{F_4n+o(n)}=O(1.4214^n)\), \((2+2^{\omega/2})^{11n/32+o(n)}=O(1.6352^n)\) and \((2+2^{\omega/2})^{7n/16+o(n)}=O(1.8699^n)\) on graphs of maximum degree \(4\), \(5\) and \(6\).
(e) The directed versions of Min Cycle Cover, Longest Path and Longest Cycle, and Exact \(k\)-Leaf Outbranching, can be solved by Monte Carlo algorithms in time \(6^{c_{3}n+o(n)}=O(1.2848^n)\) and \(6^{F_4n+o(n)}=O(1.5533^n)\) on directed graphs whose underlying undirected graph has maximum degree \(3\) and \(4\).
(f) Co-Path Packing (delete at most \(k\) vertices so that every component of the remaining graph is a path) can be solved by a Monte Carlo algorithm in time \(O^{*}(2.8192^k)\), and \(k\)-Co-Path Set (delete at most \(k\) edges so that every component of the remaining graph is a path) by a Monte Carlo algorithm in time \(O^{*}(1.5423^k)\).
(g) On graphs with \(m\) edges, Hamiltonian Cycle can be solved by a Monte Carlo algorithm in time \((2+\sqrt2)^{7m/48+o(m)}=O(1.1962^m)\), and the traveling salesperson problem with nonnegative integer edge weights deterministically in time \((2+2^{\omega/2})^{7m/48+o(m)}=O(1.2320^m)\), with \(\omega\) as in (d). For average degree at most \(d\), that is \(m\le\frac d2n\), these are \(O(1.0937^{dn})\) and \(O(1.1100^{dn})\).
The proof, in Appendix A.7.3, runs the algorithms listed above on the path decompositions of Theorem 10.1 and on the orderings of Corollary 10.2 and Theorem 10.3. The path-decomposition bounds for maximum degree \(5\) and \(6\) and those of (f) and (g) use Theorem 1.3, and hence Theorem 7.2. The cutwidth bounds for maximum degree \(4\) and \(5\) use the orderings of Theorem 3.6, which Theorem 10.3 computes in deterministic polynomial time.
Almost Forest Deletion.
Gowda, Lonkar, Panolan, Patel and Saurabh ask for at most \(k\) vertices whose deletion leaves a graph that becomes a forest after the deletion of at most \(\ell\) further edges. One of their Monte Carlo algorithms runs in time \(O^{*}(3^k\cdot1.78^\ell)\) and exponential space (Gowda et al. 2024 Theorem 1.2(4)). It applies the Cut&Count algorithm to a tree decomposition of width \(k+\frac3{5.769}\ell+O(\log\ell)\), obtained from the bound of Kneis et al. on a graph with at most \(3\ell\) edges (Gowda et al. 2024 Lemma 3.34). With Remark 9.14 in place of that bound, the width is \(k+\frac7{16}\ell+o(\ell)\), and since \(3^{7/16}<1.6172\) the running time becomes \(O^{*}(3^k\cdot1.62^\ell)\).