Appendix C Separate, Measure and Conquer: the analyses

This appendix contains the analyses behind Section 12. Appendix C.1 explains the technique operationally and shows where the separator constant enters, and Appendix C.2 gives the conventions for the computer-assisted steps. Appendix C.3 derives balanced separators from our decompositions. Appendix C.4 reruns the linear program of Gaspers and Sorkin for cubic Max 2-CSP; we show that the optimum of their linear program is exactly \(\frac{2c}{1+4c}\) as a function of the separator constant \(c\). Appendices C.5, C.6, C.7, C.8 and C.9 prove the bounds for counting independent sets and coloring.

Throughout this appendix \(r\ge2\) denotes the domain size of Max \((r,2)\)-CSP, as in Section 11.1. All logarithms without a base are binary.

C.1 The technique

This subsection describes Separate, Measure and Conquer in the generality needed below, following (Gaspers and Sorkin 2017, sec. 1.1 and 4), and isolates the one constraint in which the separator constant appears. Section, lemma and equation numbers of (Gaspers and Sorkin 2017) refer to its arXiv version (Gaspers and Sorkin 2014). The algorithm of Appendix C.4, and the subcubic part of the algorithm of Appendix C.5, are instances of this scheme.

A separation of a graph \(G\) is a partition \((L,S,R)\) of \(V(G)\) such that no edge joins \(L\) and \(R\); \(S\) is the separator, \(L\) and \(R\) are the left and right sides.

Branching on the separator.

Consider a branching algorithm that removes a vertex in every branch, as most algorithms for Max 2-CSP, counting independent sets or counting dominating sets do. Suppose it is given a separation \((L,S,R)\) of the input with \(|S|\le cn\) and \(|L|,|R|\le\frac{1-c}{2}n\), and that it always branches on a vertex of \(S\). Used on its own, the separator gives a weak bound: if branching on each separator vertex multiplies the running time by \(r\) and nothing else is gained, the running time satisfies \(t(n)=r^{cn}\cdot 2\,t(\frac{1-c}{2}n)\), whose solution is \(r^{\frac{2c}{1+c}n}\), that is \(r^{2n/7}\) for \(c=\frac16\). This is slower than the simple \(r^{n/4}\) algorithm for cubic Max 2-CSP (Scott and Sorkin 2007), which branches on any vertex and uses that its three neighbors become contractible.

A better bound comes from combining the two effects. Locally, branching on a separator vertex simplifies the instance as much as branching on any other vertex, and the split at the end comes in addition. In the cubic Max 2-CSP setting, each branching on a separator vertex removes it and makes its three neighbors contractible. If these neighbors fall on the two sides evenly, each side shrinks by \(\frac32\) per separator vertex, and the optimistic recurrence of (Gaspers and Sorkin 2017, sec. 1.1) is \[t(n)=r^{cn}\cdot 2\,t\Bigl(\frac{1-c}{2}n-\frac32\,cn\Bigr).\] With \(t(n)=r^{xn}\) this reads \(x=c+x\cdot\frac{1-4c}{2}\), so \(x=\frac{2c}{1+4c}\): for \(c=\frac16\) this is the \(\frac15\) of Gaspers and Sorkin, and for \(c=c_{3}\) it is \(0.179341\). Edwards (Edwards 2016), whose polynomial-space algorithm is also separator-based, remarks that an improved coefficient \(c<\frac16\) for cubic graphs would give the exponent \(\frac{2c}{1+4c}\) by his argument.

The measure.

The optimistic recurrence is not a proof: the branchings need not split evenly between the sides, the algorithm must sometimes move vertices between \(L\), \(S\) and \(R\) to keep branching on the separator, and the split takes effect only at the end, all at once. Gaspers and Sorkin make it rigorous with a measure that assigns weight only to the separator and to the larger side. Let \(\mu_s\) and \(\mu_r\) assign nonnegative weights to vertex sets (“separator” and “right” weights, depending on the current labeled graph), and let the sides be named so that \(\mu_r(R)\ge\mu_r(L)\). The measure is (Gaspers and Sorkin 2017, (26)) \[\begin{equation*} \tag{C.1} \mu(L,S,R)=\mu_s(S)+\mu_r(R) +\max\Bigl\{0,\,B-\frac{\mu_r(R)-\mu_r(L)}{2}\Bigr\} +(1+B)\log_{1+\eta}\bigl(\mu_r(R)+\mu_s(S)\bigr), \end{equation*}\] where \(B\) is a constant larger than the change of the imbalance \(\mu_r(R)-\mu_r(L)\) in any single transformation except the separation step below, and \(\eta>0\) is a small constant. The vertices of \(L\) carry no weight: when the separator is exhausted, the remaining running time is at most twice that for the larger side \(R\), and the smaller side is accounted for by the halving of the weight of \(R\). The third term is a penalty for balanced instances. Gaspers and Sorkin combine it with a condition on the transformations (Gaspers and Sorkin 2017 condition (30)): if \(\mu_r(R)-\mu_r(L)>B\), a transformation must decrease \(\mu_r(R)\) at least as much as \(\mu_r(L)\). Under this condition every transformation decreases \(\mu_r(R)\) plus the penalty by at least half of its total progress on the two sides. The logarithmic term offsets the penalty \(B\) that may appear each time a new separation is computed, and it contributes only a polynomial factor to the running time.

Where the separator constant enters.

Every transformation of the algorithm must satisfy the usual measure-and-conquer condition (Lemma C.1 below). For the local branching and simplification rules this gives constraints that do not involve the separator. The only transformation that does is the separation step: when \(S=\emptyset\), the instance on \(L\cup R\) is solved as two independent instances, and for each of them (say the one on \(R\)) a new separation \((L',S',R')\) is computed. The measure must not increase; the logarithmic term offsets the new penalty provided that (the case \(S=\emptyset\) of (Gaspers and Sorkin 2017, (29))) \[\begin{equation*} \tag{C.2} \mu_r(R)\ge(1+\eta)\bigl(\mu_r(R')+\mu_s(S')\bigr). \end{equation*}\]

Suppose that every vertex has right weight \(w_r\) and separator weight at most \(w_s\), where \(w_s\ge\frac{w_r}2\), and that the new separation has \(|S'|\le c|R|\) and \(|L'|=|R'|\), so that \(|R'|=\frac{|R|-|S'|}2\). Then \(\mu_r(R')+\mu_s(S')\le w_s|S'|+w_r\frac{|R|-|S'|}2\), which is nondecreasing in \(|S'|\) because \(w_s\ge\frac{w_r}2\), so it is at most \((c\,w_s+\frac{1-c}2w_r)|R|\) (this monotonicity argument is carried out in Lemma C.4). Hence (C.2) holds as soon as \[\begin{equation*} \tag{C.3} c\,w_s+\frac{1-c}{2}\,w_r<w_r,\qquad\text{equivalently}\qquad w_s<\frac{1+c}{2c}\,w_r . \end{equation*}\] The separations of Appendix C.3 have \(|S'|\le c|R|\) only up to a lower-order term; this is absorbed by taking \(c\) slightly larger than the separator constant and \(|R|\) large.

This is the mechanism by which the separator constant controls the running time. A branching on a separator vertex removes that vertex from \(S\), so its large weight \(w_s\) contributes to the decrease of the measure; the branching constraints therefore need \(w_s\) large compared with the right weights. The time bound is governed by \(w_r\), the weight of a vertex in the initial instance \((\emptyset,\emptyset,V)\). Constraint (C.3) caps the ratio \(w_s/w_r\) by \(\frac{1+c}{2c}\), which is \(3.5\) for \(c=\frac16\) and \(4.076\) for \(c=c_{3}\). A smaller separator constant relaxes the cap, and \(w_r\) can decrease. Everything else in the analysis is unchanged. Gaspers and Sorkin note that any improvement of their separator lemma improves their running times (Gaspers and Sorkin 2017, sec. 3.3); Lemma C.5 quantifies this exactly for cubic Max 2-CSP.

The analyses rest on the following lemma, which bounds the running time of a branching algorithm by a measure that decreases suitably along every branching, and allows a hand-over to a subroutine with its own measure. In it, \(A\) is an algorithm for a problem, \(\mathcal{B}\) is an algorithm for a class \(\mathcal{C}\) of instances, and \(\mu\), \(\mu_{\mathcal{B}}\) and \(\nu\) are nonnegative measures on instances.

Lemma C.1 ((Gaspers and Sorkin 2017 Lemma 4.2), (Gaspers and Lee 2023 Lemma 1)).  Let \(c_0\ge0\) and \(\lambda>1\) be constants, and let \(\mu_{\mathcal{B}}(I)\le\mu(I)\) for every \(I\in\mathcal{C}\). Suppose that on every instance \(I\), either \(I\in\mathcal C\) and \(A\) solves \(I\) by calling \(\mathcal{B}\) in time \(O(\nu(I)^{c_0+1}\lambda^{\mu_{\mathcal{B}}(I)})\), or \(A\) reduces \(I\) to instances \(I_1,\dots,I_k\), solves them recursively and combines the solutions, using time \(O(\nu(I)^{c_0})\) outside the recursive calls, where \(\nu(I_i)\le\nu(I)-1\) for every \(i\) and \[\sum_{i=1}^{k}\lambda^{\mu(I_i)}\le\lambda^{\mu(I)}.\] Then \(A\) solves every instance \(I\) in time \(O(\nu(I)^{c_0+1}\lambda^{\mu(I)})\).

The case without a subroutine \(\mathcal B\) is (Gaspers and Sorkin 2017 Lemma 2.3).

For a two-way branching with \(\lambda=2\) whose branches decrease the measure by at least \(a\) and \(b\), the condition reads \(2^{-a}+2^{-b}\le1\); we call \((a,b)\) a branching vector. For Max \((r,2)\)-CSP the branching creates \(r\) instances with the same measure \(\mu'\), and with \(\lambda=r\) the condition reads \(1+\mu'-\mu\le0\).

C.2 Computer-assisted steps

The analyses of Appendix C.4 and of Appendices C.5, C.6, C.7, C.8 and C.9 end in finitely many explicit inequalities between explicit rational weights. We list every inequality and every weight, so that each can be checked by hand or by machine. The accompanying code checks them as follows. Linear inequalities are checked in exact rational arithmetic (Python fractions). Every branching vector \((a,b)\) is checked to satisfy \(2^{-a}+2^{-b}\le1\) in interval arithmetic (mpmath.iv, 40 decimal digits), with the weights entered as exact rationals, except in the finite enumerations of configurations of Appendix C.9 (g2_enumeration.py): there the vectors are computed in exact rational arithmetic and the condition is checked in floating point, with \(40\)-digit decimal arithmetic for sums close to \(1\). Floating-point optimization (scipy) is used only to find the weights and to report optima that the theorems do not use; nothing in a proof depends on it.

C.3 Balanced separators from the decompositions

The previous analyses obtain their separators from the bounds of Fomin and Høie and of Fomin, Gaspers, Saurabh and Stepanov (Fomin and Høie 2006; Fomin et al. 2009): Gaspers and Sorkin use separators of size \(\alpha_\Delta|V|+o(|V|)\) with \(\alpha_3,\alpha_4,\alpha_5,\alpha_6=\frac16,\frac13,\frac{13}{30},\frac{23}{45}\) (Gaspers and Sorkin 2017 Lemmas 1.2 and 4.1), and Gaspers and Lee use \(\frac{n_3}{6}\) (Gaspers and Lee 2023). The following lemma provides the same kind of separators from our decompositions. Part (a) is used for Max 2-CSP, part (b) for counting independent sets.

Let \(a^*_3=c_{3}\), \(a^*_4=F_4\), \(a^*_5=\frac{11}{32}\) and \(a^*_6=\frac7{16}\). For a graph \(G\) and \(\theta>0\), a function \(\mu_r\) from the subsets of \(V(G)\) to \([0,\infty)\) is \(\theta\)-Lipschitz if \(\mu_r(\emptyset)=0\) and \(|\mu_r(X\cup\{v\})-\mu_r(X)|\le\theta\) for all \(X\subseteq V(G)\) and \(v\in V(G)\). We write \(V_3\) for the set of vertices of degree \(3\) of \(G\), so that \(n_3=|V_3|\).

Lemma C.2 (balanced separators).  Let \(\theta>0\).

(a)  Let \(3\le\Delta\le6\). There is a function \(\rho'_\Delta(x)=o(x)\) such that for every graph \(G\) with \(\Delta(G)\le\Delta\) and every \(\theta\)-Lipschitz \(\mu_r\) computable in polynomial time, a separation \((L,S,R)\) of \(G\) with \(|S|\le a^*_\Delta|V(G)|+\rho'_\Delta(|V(G)|)\) and \(|\mu_r(L)-\mu_r(R)|\le\theta\) can be computed deterministically in polynomial time; if \(\mu_r(X)=|X|\), it can moreover have \(|L|=|R|\).

(b)  There is a function \(\rho_3(x)=o(x)\) such that for every graph \(G\) with \(\Delta(G)\le3\) and \(\delta(G)\ge2\) and every \(\theta\)-Lipschitz \(\mu_r\) computable in polynomial time with \(\mu_r(X)=\mu_r(X\cap V_3)\) for all \(X\), a separation \((L,S,R)\) of \(G\) with \(S\subseteq V_3\), \(|S|\le c_{3}n_3+\rho_3(n_3)\) and \(|\mu_r(L)-\mu_r(R)|\le\theta\) can be computed deterministically in polynomial time.

For comparison, \(c_{3}<\frac16\), \(F_4<0.2458<\frac13\), \(\frac{11}{32}<\frac{13}{30}\) and \(\frac7{16}<\frac{23}{45}\). The proof is the argument of (Gaspers and Sorkin 2017 Lemma 4.1): a nice path decomposition gives a sequence of separations whose separators are its bags, and the difference of \(\mu_r\) between the two sides changes by at most \(\theta\) from one separation to the next. Part (b) applies this to the cubic multigraph obtained by suppressing the vertices of degree \(2\).

Proof. We first show how a path decomposition yields the separation. Let \(H\) be a graph and \((W_1,\dots,W_t)\) a path decomposition of \(H\) of width \(w\) in which consecutive bags differ in exactly one vertex (a nice path decomposition). Every path decomposition, given for instance in the interval form of Theorem 10.1, can be turned into a nice one of the same width with at most \(2|V(H)|\) bags in polynomial time: list the bags, and between two consecutive bags first remove the vertices of \(W_i\setminus W_{i+1}\) one at a time, then add those of \(W_{i+1}\setminus W_i\) one at a time; start with the empty bag and end by removing the last vertices one at a time (empty bags are discarded at the end). For \(1\le i\le t\) let \[L_i=\Bigl(\bigcup_{j<i}W_j\Bigr)\setminus W_i,\qquad R_i=V(H)\setminus(L_i\cup W_i).\] Then \((L_i,W_i,R_i)\) is a separation: a vertex of \(L_i\) occurs only in bags before \(W_i\) and a vertex of \(R_i\) only in bags after \(W_i\), so by the interval property no bag contains both, and they are not adjacent. Let \(f(i)=\mu_r(L_i)-\mu_r(R_i)\). If \(W_{i+1}=W_i\cup\{v\}\), then \(v\in R_i\), \(L_{i+1}=L_i\) and \(R_{i+1}=R_i\setminus\{v\}\); if \(W_{i+1}=W_i\setminus\{v\}\), then \(L_{i+1}=L_i\cup\{v\}\) and \(R_{i+1}=R_i\). In both cases \(|f(i+1)-f(i)|\le\theta\), and in both cases \(|L_i|-|R_i|\) increases by exactly one. Moreover \(L_1=\emptyset\) and \(R_t=\emptyset\), so \(f(1)=-\mu_r(R_1)\le0\le\mu_r(L_t)=f(t)\). Let \(i\) be the largest index with \(f(i)\le0\). If \(i=t\) then \(f(t)=0\); otherwise \(f(i+1)>0\) and \(f(i)\ge f(i+1)-\theta>-\theta\). Either way \(|f(i)|\le\theta\). For \(\mu_r(X)=|X|\) the integer \(|L_i|-|R_i|\) increases by exactly one at each step, from at most \(0\) to at least \(0\), so it vanishes at some \(i\). All of this takes polynomial time, and the separator \(W_i\) has at most \(w+1\) vertices.

(a) Let \(n=|V(G)|\). By Theorem 10.1(b) a path decomposition of \(G\) of width at most \(W(G)+\rho(n)\), with \(\rho(n)=o(n)\), is computed deterministically in polynomial time, where \(W(G)\) is the respective bound: \(c_{3}n\) by Theorem 8.1 if \(\Delta\le3\); \(F_4n\) by Theorem 7.1(a) if \(\Delta\le4\); \(\frac5{32}n_3+\frac14n_4+\frac{11}{32}n_5\le\frac{11}{32}n\) by Theorem 7.2 with the triple \(\mathsf{S}\) if \(\Delta\le5\); and \(\sum_{d\le6}a_dn_d\le a_6n=\frac7{16}n\) by Theorem 1.3 if \(\Delta\le6\). (Vertices of degree at most \(2\) have coefficient \(0\) in these bounds, and the coefficients are nondecreasing in \(d\).) So \(W(G)\le a^*_\Delta n\), and the construction above gives a separation with \(|S|\le a^*_\Delta n+\rho(n)+1\). This is one algorithm for each \(\Delta\), and \(\rho\) depends only on \(\Delta\) (through the case of Theorem 10.1 used); take \(\rho'_\Delta(x)=\rho(x)+1\).

(b) Suppress the vertices of degree \(2\): every component of \(G\) that is a cycle contains no vertex of \(V_3\), and in every other component each vertex of degree \(2\) lies on a unique path \(u\,x_1\cdots x_q\,w\) whose ends \(u,w\) (possibly equal) are in \(V_3\) and whose inner vertices have degree \(2\). Replacing every such path by an edge \(uw\) gives a multigraph \(M\) (possibly with loops and parallel edges) on \(V_3\) in which every vertex has degree \(3\). Let \(G_M\) be the underlying simple graph, without loops; \(\Delta(G_M)\le3\). By Theorem 8.1 and Theorem 10.1(b) a path decomposition of \(G_M\) of width at most \(c_{3}n_3+\rho(n_3)\) is computed deterministically in polynomial time, and the construction above, applied with \(\mu_r\) restricted to \(V_3\), yields a separation \((L_M,S,R_M)\) of \(G_M\) with \(|S|\le c_{3}n_3+\rho(n_3)+1\) and \(|\mu_r(L_M)-\mu_r(R_M)|\le\theta\). Extend it to \(G\): put every cycle component and every suppressed path whose ends lie in \(L_M\cup S\) into \(L\), and every other suppressed path into \(R\); the ends of a suppressed path are adjacent or equal in \(M\), so they never lie in \(L_M\) and \(R_M\) respectively. Then \((L,S,R)\) with \(L\supseteq L_M\), \(R\supseteq R_M\) is a separation of \(G\) with \(S\subseteq V_3\), and \(\mu_r(L)=\mu_r(L_M)\), \(\mu_r(R)=\mu_r(R_M)\) because \(\mu_r\) depends only on degree-\(3\) vertices. Take \(\rho_3(x)=\rho(x)+1\).  ∎

C.4 Max 2-CSP

This subsection reruns the analysis of Gaspers and Sorkin (Gaspers and Sorkin 2017, sec. 3) for cubic Max \((r,2)\)-CSP with the separators of Lemma C.2(a), and lifts the result to all instances with the theorem of Scott and Sorkin. For cubic instances the exponent drops from the \(\frac n5\) of Gaspers and Sorkin to \(\frac{2c_{3}}{1+4c_{3}}n+o(n)<0.179341n+o(n)\) (Theorem C.3). The algorithm is that of Gaspers and Sorkin, rules R1–R9, with the separations of Lemma C.2(a). Only one constraint of their linear program involves the separator constant (Lemma C.4), and we solve the program exactly as a function of that constant \(c\): its optimum is \(\frac{2c}{1+4c}\), with explicit weights and a three-line dual certificate (Lemma C.5). At \(c=\frac16\) these are the weights of Gaspers and Sorkin.

Put \[\gamma=\frac{2c_{3}}{1+4c_{3}}\qquad\text{and}\qquad\alpha=\frac{2\gamma}{3}.\] RCSP and PCSP are the ring and polynomial versions of Section 11.1, and polynomially bounded PCSP is meant in the sense of Scott and Sorkin (Scott and Sorkin 2009).

Theorem C.3 (polynomial-space Max 2-CSP).  Max \((r,2)\)-CSP with \(n\) variables and \(m\) constraints can be solved in polynomial space and time

(a)  \(r^{\gamma n+o(n)}=r^{\alpha m+o(m)}\) if the constraint graph is cubic;

(b)  \(r^{(\frac18+\frac38\alpha)m+o(m)}\) if the constraint graph has maximum degree at most \(4\);

(c)  \(r^{(\frac7{50}+\frac3{10}\alpha)m+o(m)}\) for all instances.

The same bounds hold for the number of ring operations of RCSP and for the running time of polynomially bounded PCSP. The numbers of dominating sets of each size of an \(n\)-vertex graph of maximum degree at most \(3\) can be computed in polynomial space and time \(3^{\gamma n+o(n)}\).

Here \(\gamma<0.179341\), \(\alpha<0.119561\), \(\frac18+\frac38\alpha<0.169836\), \(\frac7{50}+\frac3{10}\alpha<0.175869\) and \(3^{\gamma}<1.21778\), so the last bound is \(O(1.2178^n)\). The polynomially bounded PCSPs include counting cuts by size and the Ising partition function.

The previous bounds are \(r^{n/5}\), \(r^{7m/40}\), \(r^{9m/50}\) and \(3^{n/5}=O(1.2458^n)\) (Gaspers and Sorkin 2017 Theorems 3.1–3.3 and 5.1); Edwards (Edwards 2016) also obtains \(r^{9m/50+o(m)}\) in polynomial space. In exponential space, Theorem 11.3 is faster. In polynomial space, this route does not improve Max 2-SAT, which is solved in time \(O^{*}(2^{m/6.321})\) (Gaspers and Sorkin 2012 Theorem 4), nor counting the dominating sets of general graphs, which takes time \(O(1.5183^n)\) (Gaspers and Sorkin 2017 Theorem 5.2): a separator constraint of that analysis is not tight, so the new separators do not lower this bound.

Reductions.

Instances are as in Section 11.1. Scott and Sorkin (Scott and Sorkin 2007) use four reductions, each computable in polynomial time: a vertex of degree \(0\) is deleted after maximizing its score (Reduction 0); a vertex of degree \(1\) is folded into its neighbor (Reduction 1); a vertex of degree \(2\) is replaced by an edge between its two neighbors, merged with an existing edge if there is one (Reduction 2); and a vertex \(v\) of degree at least \(3\) is branched on (Reduction 3): for each color \(C\in[r]\), \(v\) is deleted and its score functions are absorbed into those of its neighbors, which gives \(r\) instances with the common constraint graph \(G-v\). An optimal solution of the instance is obtained in polynomial time from optimal solutions of the subinstances.

The algorithm.

The algorithm maintains a separation \((L,S,R)\) of the current constraint graph \(G\), initially \((\emptyset,\emptyset,V)\). Let \(L_3,S_3,R_3\) denote the vertices of degree \(3\) in \(L,S,R\), let \(S_2\) denote the vertices of degree \(2\) in \(S\), and name the sides so that \(|L_3|\le|R_3|\). The measure is (Gaspers and Sorkin 2017, (6)) \[\begin{equation*} \begin{gathered}\tag{C.4} \mu(L,S,R)=w_s|S_3|+w_{s,2}|S_2|+w_r|R_3|+w_b\mathbf{1}(|R_3|=|L_3|)\\ +w_c\mathbf{1}(|R_3|=|L_3|+1)+w_d\log_{3/2}(|R_3|+|S_3|), \end{gathered} \end{equation*}\] a special case of (C.1) with integral imbalance: \(w_b\) and \(w_c\) play the role of the penalty, and the logarithm that of the last term. The algorithm applies the first applicable rule of the following list; when a rule is described, the earlier rules are assumed not to apply. The constraint numbers refer to Table 9.

R1.  Degree \(0\). Apply Reduction 0. The measure does not change.

R2.  Half-edge deletion. If some vertex has degree \(1\), or a vertex of \(L\cup R\) has degree \(2\), apply Reduction 1 or 2. Viewing every edge deletion as two half-edge deletions, each lowering one degree, the measure does not increase under constraints (7)–(11). From now on the graph is cubic except for vertices of degree \(2\) in \(S\).

R3.  Separation. If \(S=\emptyset\): the instance is the disjoint union of the instances on \(L\) and \(R\), which are solved independently. For each of them a new separation is computed by Lemma C.2(a) with \(\mu_r(X)=|X|\). Constraint \((12_c)\) below.

R4.  Degree \(2\) in \(S\). If \(s\in S\) has degree \(2\), apply Reduction 2. If its neighbors are \(u_1\in L\) and \(u_2\in R\), the new edge \(u_1u_2\) would join the sides, so \(u_2\) is moved into \(S\). Constraints (13)–(15).

R5.  No neighbor in \(L\). If \(s\in S\) has no neighbor in \(L\), move it into \(R\) (“drag” it). Constraint (16).

R6.  No neighbor in \(R\). If \(s\in S\) has no neighbor in \(R\), move it into \(L\) (swapping the names of the sides if \(|R_3|=|L_3|\)). Constraints (17), (18).

R7.  One neighbor in each of \(L\), \(S\), \(R\). Branch on such an \(s\). Constraint (19).

R8.  Two neighbors in \(L\). Let \(s\in S\) have two neighbors in \(L\) and one, \(u\), in \(R\). If \(|R_3|\le|L_3|+1\), branch on \(s\); constraints (20), (21). Otherwise move \(s\) into \(L\) and \(u\) into \(S\); constraint (22).

R9.  Two neighbors in \(R\). Otherwise every \(s\in S\) has two neighbors in \(R\) and one in \(L\); branch on such an \(s\). Constraints (23), (24), and (20) after swapping the sides when \(|R_3|=|L_3|\).

Every rule takes polynomial time. The rules that only move vertices between \(L\), \(S\) and \(R\) decrease the secondary measure \(\nu=3|S_3|+2|R_3|+|L_3|+2|E(G)|\) (Gaspers and Sorkin 2017 end of Section 3.2), and so do all rules that delete vertices; Lemma C.4 treats the separation step R3.

Table 9: The constraints of the cubic Max 2-CSP analysis (Gaspers and Sorkin 2014, sec. 3.2), each in the form “expression \(\le0\)”. In \((12_c)\) the previous value \(c=\frac16\) is replaced by the separator constant \(c\). The last column gives the expression for the weights of Lemma C.5, multiplied by \(D=1+4c\); a constant term \(1\) becomes \(D\).

No.	Rule (case)	Constraint	\(D\cdot\text{(value at \href{#lem:lp}{Lemma~C.5})}\)
(7)	measure nonnegative	\(w_s,w_{s,2},w_r,w_b,w_c,w_d\ge0\)	\(\text{holds}\)
(8)	R2, degree \(3\to2\) in \(L\)	\(-w_b+w_c\)	\(-c\)
(9)	R2, degree \(3\to2\) in \(S\)	\(-w_s+w_{s,2}\)	\(-c\)
(10)	R2, degree \(3\to2\) in \(R\)	\(-w_r+w_c\)	\(-c\)
(11)	R2, degree \(3\to2\) in \(R\)	\(-w_r+w_b-w_c\)	\(-c\)
\((12_c)\)	R3, separation	\(c\,w_s+\frac{1-c}{2}w_r-w_r\)	\(0\)
(13)	R4, balanced	\(-w_{s,2}+w_s-w_b+w_c\)	\(0\)
(14)	R4, imbalanced	\(-w_{s,2}+w_s-w_r+w_c\)	\(0\)
(15)	R4, imbalanced	\(-w_{s,2}+w_s-w_r+w_b-w_c\)	\(0\)
(16)	R5	\(-w_s+w_r\)	\(c-1\)
(17)	R6	\(-w_s+w_c\)	\(-1\)
(18)	R6	\(-w_s+w_b-w_c\)	\(-1\)
(19)	R7, branch	\(1-2w_s+w_{s,2}-w_r\)	\(0\)
(20)	R8, branch	\(1-w_s-w_r-w_b+w_c\)	\(0\)
(21)	R8, branch	\(1-w_s-w_r-w_c\)	\(0\)
(22)	R8, drag	\(-w_r+w_b\)	\(0\)
(23)	R9, branch	\(1-w_s-2w_r-w_c+w_b\)	\(0\)
(24)	R9, branch	\(1-w_s-2w_r+w_c\)	\(0\)

Table 9 lists the constraints. They are derived in (Gaspers and Sorkin 2017, sec. 3.2) from the condition of Lemma C.1: for the rules that create one instance the measure must not increase, and for a branching on a vertex, which creates \(r\) instances of the same measure \(\mu'\), the condition \(r\cdot r^{\mu'}\le r^{\mu}\) is \(1+\mu'-\mu\le0\). For example, in R7 the separator loses the degree-\(3\) vertex \(s\), its neighbor in \(S\) drops to degree \(2\), and one degree-\(3\) vertex of \(R\) and one of \(L\) drop to degree \(2\); the balance is unchanged, which gives (19). We do not repeat the other derivations; the only one that involves the separator is that of \((12_c)\). In the following lemma, an instance with fewer than \(N_0\) vertices that arises in the Separation rule R3 is counted as a leaf of measure \(0\).

Lemma C.4 (the separation constraint).  Let \(0<c<\frac13\), and suppose that R3 uses separations with \(|S'|\le c|V|\) and \(|L'|=|R'|\) on every cubic graph with \(|V|\ge N_0\) to which it applies. If the weights satisfy (7), \((12_c)\) and (16) of Table 9 and \(w_d=w_b+1\), then on every instance with \(|R|\ge N_0\), R3 satisfies the condition of Lemma C.1 and decreases the secondary measure \(\nu\).

Proof. We follow (Gaspers and Sorkin 2017, sec. 3.2, Separation). Let the instance be \((L,\emptyset,R)\) with \(N=|R|\ge|L|\). Since R1 and R2 do not apply and \(S\) is empty, every vertex has degree \(3\), so \(N=|R_3|\), and \(\mu\ge w_rN+w_d\log_{3/2}N\) because the penalty terms are nonnegative. The graph \(G[R]\) is cubic, since \(S=\emptyset\) and no edge joins \(L\) and \(R\). Let \((L',S',R')\) be the new separation of \(G[R]\) and \(s=|S'|\le cN\). It is balanced (\(|L'_3|=|R'_3|\)), so its measure is \[\mu'=w_ss+w_r\frac{N-s}{2}+w_b+w_d\log_{3/2}\frac{N+s}{2}.\] The derivative of \(w_ss+w_r\frac{N-s}{2}\) in \(s\) is \(w_s-\frac{w_r}2\ge0\) by (16) and (7), so this part is at most \((c\,w_s+\frac{1-c}2w_r)N\). Since \(c<\frac13\) we have \(\frac{N+s}{2}\le\frac{1+c}{2}N\le\frac23N\), hence \(w_d\log_{3/2}\frac{N+s}2\le w_d\log_{3/2}N-w_d\). With \(w_d=w_b+1\), \[\mu'\le\Bigl(c\,w_s+\frac{1-c}{2}w_r\Bigr)N+w_d\log_{3/2}N-1 \le w_rN+w_d\log_{3/2}N-1\le\mu-1\] by \((12_c)\). The instance on \(L\) has measure \(\mu''\le\mu-1\) by the same bound with \(|L|\le N\) in place of \(N\), since the bound is nondecreasing in \(N\); if \(|L|<N_0\), it is a leaf of measure \(\mu''=0\le\mu-1\). Since \(r\ge2\), \(r^{\mu'}+r^{\mu''}\le2r^{\mu-1}\le r^{\mu}\). For the secondary measure: if \(L\ne\emptyset\), splitting \((L,\emptyset,R)\) into \((\emptyset,\emptyset,R)\) and \((\emptyset,\emptyset,L)\) decreases \(\nu\) because \(|L|\le|R|\) and both sides are nonempty; if \(L=\emptyset\), as for the initial instance, this first step is void. Replacing \((\emptyset,\emptyset,R)\) by \((L',S',R')\) changes \(\nu\) by \(3s+2|R'|+|L'|-2N=s-|L'|=s-\frac{N-s}{2}<0\), because \(s\le cN<\frac N3\).  ∎

Thus the separator constant enters the linear program only through \((12_c)\), and the proof once more through \(c<\frac13\) (the logarithmic estimate and the secondary measure). The previous derivation estimates \(|R'_3|\le\frac5{12}|R_3|\) and \(|S'_3|\le\frac16|R_3|+o(|R_3|)\) separately; the monotonicity in \(s\) used above shows that the combined form \((12_c)\) is what is needed for every separator fraction \(c<\frac13\).

Lemma C.5 (the linear program).  For every \(c\in(0,1]\) the weights \[w_s=\frac{1+c}{1+4c},\quad w_{s,2}=\frac{1}{1+4c},\quad w_r=w_b=\frac{2c}{1+4c},\quad w_c=\frac{c}{1+4c},\quad w_d=w_b+1\] satisfy every constraint of Table 9. Conversely, every solution of (12\(_c\)), (21) and (24) has \(w_r\ge\frac{2c}{1+4c}\). Hence the minimum of \(w_r\) subject to the constraints of Table 9 is exactly \(\frac{2c}{1+4c}\).

Code: constants.py

Proof. Put \(D=1+4c\) and multiply all weights by \(D\): the scaled weights are \(w_s=1+c\), \(w_{s,2}=1\), \(w_r=w_b=2c\) and \(w_c=c\), and the constant \(1\) in (19)–(21), (23) and (24) becomes \(D\). Substituting gives the last column of Table 9: (8)–(11) each equal \(-c\); \((12_c)\) equals \(c(1+c)+\frac{1-c}{2}\cdot2c-2c=0\); (13) equals \(-1+(1+c)-2c+c=0\), (14) equals (13) because \(w_r=w_b\), and (15) equals \(-1+(1+c)-2c+2c-c=0\); (16) equals \(c-1\le0\); (17) and (18) equal \(-1\); (19) equals \(D-2(1+c)+1-2c=0\); (20) equals \(D-(1+c)-2c-2c+c=0\); (21) equals \(D-(1+c)-2c-c=0\); (22) equals \(0\); (23) equals \(D-(1+c)-4c-c+2c=0\); and (24) equals \(D-(1+c)-4c+c=0\). All weights are nonnegative, so (7) holds.

For the converse, \((12_c)\) says \(w_s\le\frac{1+c}{2c}w_r\), and the sum of (21) and (24) says \(2\le2w_s+3w_r\). Together, \(2\le(\frac{1+c}{c}+3)w_r=\frac{1+4c}{c}w_r\).  ∎

At \(c=\frac16\) these are the previous weights \((w_s,w_{s,2},w_r,w_b,w_c)=(0.7,0.6,0.2,0.2,0.1)\) (Gaspers and Sorkin 2017, sec. 3.2), and the tight constraints are those listed there, (12)–(15) and (19)–(24). Gaspers and Sorkin solved the program numerically. The value \(\frac{2c}{1+4c}\) is the exponent of the optimistic recurrence, and Edwards notes that his argument would give it for an improved separator coefficient (Appendix C.1); Lemma C.5 adds that it is the exact optimum of the linear program of Gaspers and Sorkin for every \(c\), with the explicit weights and the certificate \((12_c)+(21)+(24)\). The accompanying code confirms both (exact check of the weights for several rational \(c\), and numerical optima at \(c=\frac16,c_{3},0.1,0.3\)).

We now prove Theorem C.3.

Proof. We prove (a) with the weights of Lemma C.5 and Lemma C.1, and obtain (b) and (c) from (a) by the lifting theorem of Scott and Sorkin. The ring versions reuse the search tree of (a), and the count of dominating sets reuses its analysis with \(r=3\).

(a) The algorithm is that of Gaspers and Sorkin, rules R1–R9, with the separations of Lemma C.2(a) for \(\Delta=3\) and \(\mu_r(X)=|X|\). Since that lemma gives one algorithm, this algorithm has no parameter; \(\varepsilon\) and \(N_0\) below enter only the analysis. Fix \(\varepsilon\in(0,\frac1{10})\), put \(c=c_{3}+\varepsilon<\frac13\), and choose \(N_0\) such that \(\rho'_3(x)\le\varepsilon x\) for \(x\ge N_0\). For the analysis, an instance with fewer than \(N_0\) vertices that arises in the Separation rule is a leaf: the algorithm runs on it as usual, and its running time is bounded by a constant \(C_\varepsilon\). By Lemma C.2(a) the separations computed on larger instances satisfy \(|S'|\le c|V|\) and \(|L'|=|R'|\). By Lemma C.5 the weights of the lemma for this \(c\) satisfy every constraint of Table 9, and \(w_d=w_b+1\). By Lemma C.4 and the derivations of (Gaspers and Sorkin 2017, sec. 3.2) for the other rules, every rule satisfies the condition of Lemma C.1 with \(\lambda=r\), and \(\nu\) decreases in every step. So the number of leaves of the search tree is at most \(r^{\mu}\) for the initial measure \[\mu(\emptyset,\emptyset,V)=w_r n+w_d\log_{3/2}n=\frac{2c}{1+4c}\,n+O(\log n),\] and, since \(\nu\) is polynomial in \(n\) and each step takes polynomial time, the running time is \(C_\varepsilon\,r^{\frac{2c}{1+4c}n}\mathop{\mathrm{poly}}(n)\). The function \(c\mapsto\frac{2c}{1+4c}\) is continuous, so letting \(\varepsilon\to0\) gives \(r^{\gamma n+o(n)}\) for the one algorithm. The recursion depth is polynomial and each call uses polynomial space, so the space is polynomial. For a cubic graph \(m=\frac32n\), so \(\gamma n=\alpha m\).

(b), (c) Scott and Sorkin (Scott and Sorkin 2007 Theorem 22) show that an algorithm solving cubic instances in time \(O^*(r^{\alpha' m})\) with \(\frac19\le\alpha'\le\frac15\) yields one solving instances of maximum degree \(4\) in time \(O^*(r^{(\frac18+\frac38\alpha')m})\) and arbitrary instances in time \(O^*(r^{(\frac7{50}+\frac3{10}\alpha')m})\); the new algorithm uses the cubic one as a subroutine and is in polynomial space if the subroutine is (Gaspers and Sorkin 2017, sec. 3.3). This is how Gaspers and Sorkin obtain \(\frac7{40}\) and \(\frac9{50}\) from \(\alpha'=\frac2{15}\). Our cubic algorithm runs in time \(O^*(r^{(\alpha+\varepsilon)m})\) for every \(\varepsilon>0\), and \(\alpha\approx0.1195606\in[\frac19,\frac15]\), so the lifted algorithm runs in time \(O^*(r^{(\frac18+\frac38(\alpha+\varepsilon))m})\) and \(O^*(r^{(\frac7{50}+\frac3{10}(\alpha+\varepsilon))m})\) for every small \(\varepsilon>0\); again the algorithm does not depend on \(\varepsilon\).

RCSP and PCSP: Gaspers and Sorkin (Gaspers and Sorkin 2017 Theorems 3.2 and 3.3) obtain their bounds by running the same algorithm with the ring versions of Reductions 0–3 of Scott and Sorkin (Scott and Sorkin 2009), which change the constraint graph exactly as the original reductions and cost \(O(r^3)\) ring operations each. The search tree, and hence the analysis, is that of (a); the lift to maximum degree \(4\) and to all instances is the same.

Dominating sets: Gaspers and Sorkin (Gaspers and Sorkin 2017, sec. 5.1, Theorem 5.1) count the dominating sets of every size of a subcubic graph \(G\) by branching, with a three-way branching (“in”, “optional”, “forbidden”), on the vertices of the cubic structure of \(G\), the cubic multigraph obtained by contracting the edges at vertices of degree at most \(2\). The pivot is chosen exactly as in the Max 2-CSP algorithm, the analysis is that of cubic Max \((3,2)\)-CSP, and instances whose cubic structure has at most a constant number \(A\) of vertices are solved in polynomial time by dynamic programming over a tree decomposition of width at most \(A\). We use the separations of Lemma C.2(a) of the underlying simple graph of the cubic structure (a separation of it is one of the multigraph) and take \(A\ge N_0\). The analysis of (a) with \(r=3\) gives \(3^{\gamma n+o(n)}\).  ∎

C.5 Counting independent sets, and graph coloring

Gaspers and Lee (Gaspers and Lee 2023) count the independent sets of a graph in polynomial space with a branching algorithm whose subcubic part is a Separate, Measure and Conquer subroutine. It branches on the vertices of a balanced separator, computed from a path decomposition (Lemma C.2), until the graph falls apart into two halves that are counted independently; a measure that gives the separator vertices extra weight (Appendix C.1) makes the measure drop at each branching on a separator vertex by enough to cover the extra weight of the separator. They extend the measure to maximum degree \(4\) and to all graphs with Wahlström’s compound measures (Wahlström 2008), and they compute the chromatic number from these counts with the inclusion–exclusion method of Björklund, Husfeldt and Koivisto (Björklund, Husfeldt, and Koivisto 2009). The separator constant \(\frac16\) enters their subcubic analysis in two places, the separator constraint and the function \(g(d)\) of (Gaspers and Lee 2023 Lemma 3). A better pathwidth bound shortens the separator phase, and the gain carries over to the larger degrees and to the chromatic number. With \(c_{3}\) in place of \(\frac16\) (Lemma C.2(b)) and the changes to the algorithm described below, their analysis, adapted, gives the following bounds.

Theorem C.6 (counting independent sets, and coloring).  Let \(G\) be a graph with \(n\) vertices. The number of independent sets of \(G\) can be computed

(a)  in polynomial space and time \(O(1.1304^n)\) if \(\Delta(G)\le3\);

(b)  in polynomial space and time \(O(1.2037^n)\) if \(\Delta(G)\le4\);

(c)  in polynomial space and time \(O(1.2341^n)\), and the chromatic number of \(G\) in polynomial space and time \(O(2.2341^n)\);

(d)  in time and space \(O(1.2287^n)\).

The previous bounds are \(O(1.1389^n)\), \(O(1.2070^n)\), \(O(1.2356^n)\), \(O(2.2356^n)\) and \(O(1.2330^n)\) (Gaspers and Lee 2023 Lemmas 5 and 6, Theorems 1 and 2). The proof of Theorem C.6, in the rest of this appendix, is computer-assisted. It runs the analysis of Gaspers and Lee with \(c_{3}\) in place of \(\frac16\), with three changes. First, the analysis of their subcubic subroutine lacks condition (30) of Gaspers and Sorkin (Gaspers and Sorkin 2017) (Appendix C.1), without which a step that crosses the balance threshold of the measure can decrease the measure by less than its branching vector counts. Their local analysis also has some further minor gaps. Fixing condition (30) increases the running time given by the analysis; for maximum degree \(3\) we obtain \(O(1.1304^n)\). In exchange, the new pathwidth bound makes the special treatment of so-called spider vertices (the separator vertices to which their subroutine gives a larger weight) unnecessary: in our subroutine every separator vertex has the same weight, which gives a simpler algorithm and analysis. Second, above maximum degree \(3\) their branching on lazy \(2\)-separators need not satisfy the measure condition of Lemma C.1 (Proposition C.26); our rule tests that condition in exact rational arithmetic. Third, we prove two steps that their paper leaves unproved, the branching vectors of their Lemma 8 for degrees \(5\) and \(6\) and a vector for the lazy rule (Proposition C.12).

A recent claim of \(O^*(1.2321^n)\) for counting independent sets (De Ita Luna et al. 2026) would beat part (c) of Theorem C.6, but not part (d). Its proof is not valid. For instance, its Lemma 3 asserts \(|E(G)|\le c\,|V(G)|\) for every graph \(G\) and vertex \(v\), with \(c=\max\{\delta(N[v])/(2|N[v]|),\,\Delta(G-N[v])/2\}\) and \(\delta(N[v])\) the sum of the degrees of the vertices of \(N[v]\); for \(G=K_{2,3}\) and \(v\) on the side of size \(2\), \(c=\frac98\) and \(|E(G)|=6>\frac{45}8\). Moreover, the analysis takes the maximum of bounds obtained in two different measures.

We prove part (a) of Theorem C.6 in Appendix C.6, and parts (b)–(d) in Appendix C.7, using two steps proved in Appendices C.8 and C.9. Numbering refers to the journal version of Gaspers and Lee (Gaspers and Lee 2023). The computer-assisted steps follow the paragraph conventions of Appendix C.2; the scripts named below are in experiments/algorithmic-consequences of the accompanying code.

The algorithm of Gaspers and Lee.

The algorithm #IS (Gaspers and Lee 2023, sec. 3) computes a weighted count of independent sets, the weights (a cardinality function) recording earlier steps. It solves graphs of maximum degree at most \(2\) in polynomial time and splits a disconnected graph into its components. Otherwise it picks a vertex \(x\) of maximum degree that maximizes the associated average degree of Wahlström (Wahlström 2008), and applies, in this order: the multiplier reduction, which folds a part of constant size attached at a cut vertex \(v\) into the cardinality function of \(v\) and deletes it; a branching for a lazy \(2\)-separator (defined in Appendix C.7); if \(\Delta(G)=3\) and no vertex of degree \(3\) has all neighbors of degree \(3\) (a \((3,3,3)\) vertex), a Separate, Measure and Conquer subroutine; otherwise it branches on \(x\), counting the independent sets of \(G-x\) and of \(G-N[x]\). All rules only delete vertices, so degrees never increase, and for \(\Delta(G)\le3\) no rule creates a \((3,3,3)\) vertex (it would have been one before).

C.6 Maximum degree 3

Skeletons.

Let \(G\) be a graph with \(\Delta(G)\le3\) and \(\delta(G)\ge2\), and let \(V_3\) be its set of vertices of degree \(3\). A \(2\)-path is a path of length at least \(2\) whose inner vertices have degree \(2\) and whose ends lie in \(V_3\). The skeleton of \(G\) is the multigraph on \(V_3\) with one edge for every edge of \(G\) inside \(V_3\) and one edge for every \(2\)-path. Every vertex of the skeleton has degree \(3\), a loop counted twice; a loop at \(v\) makes \(v\) a cut vertex. The far end of a skeleton edge at \(v\) is a skeleton neighbor of \(v\). For a separation \((L,S,R)\) with \(S\subseteq V_3\), the inner vertices of a \(2\)-path lie all in \(L\) or all in \(R\), so no skeleton edge joins \(L\) and \(R\). For \(v\in S\) let \(e_L(v)\), \(e_R(v)\) and \(e_S(v)\) be the numbers of skeleton edges at \(v\) whose far end lies in \(L\), \(R\) and \(S\).

The measure.

Let \(r_3,s_3>0\) be weights, \(B=42r_3\) and \(J=40r_3\). For a separation \((L,S,R)\) let \(a=r_3|R\cap V_3|\), \(b=r_3|L\cap V_3|\), \(\Xi(a,b)=\max\{a,b,\frac{a+b}2+B\}\), let \(\eta>0\), and let \(\Lambda(x)=(1+B)\log_{1+\eta}\max\{1,x\}\). The measure of a separated instance is \[\begin{equation*} \tag{C.5} \mu_{\mathrm{sep}}(L,S,R)=s_3|S|+\Xi(a,b)+\Lambda\bigl(\max\{a,b\}+s_3|S|\bigr). \end{equation*}\] This is (C.1) with \(\mu_r(X)=r_3|X\cap V_3|\) and \(\mu_s(X)=s_3|X|\), written symmetrically in the sides. It is nondecreasing in \(a\), \(b\) and \(|S|\). We name the sides so that \(a\ge b\) and call \(t=a-b\) the imbalance. Each of the three linear pieces \(a\), \(b\), \(\frac{a+b}2+B\) of \(\Xi\) is at most \(\Xi\), and one of them attains it. Hence, if \((a,b)\) changes to \((a',b')\) and \(\pi\) is a piece that attains \(\Xi(a',b')\), \[\begin{equation*} \tag{C.6} \Xi(a',b')-\Xi(a,b)\le\pi(a',b')-\pi(a,b). \end{equation*}\] This inequality, together with the pull rule (S6) below, replaces condition (30) of Gaspers and Sorkin (Gaspers and Sorkin 2017) (Appendix C.1).

The algorithm.

Let \(N_0\) be a constant and \(K_0=8\). To count directly a graph of maximum degree at most \(3\) with at most \(N_0\) vertices of degree \(3\) means to run the standard dynamic program over a path decomposition of width \(N_0+2\) (deleting the vertices of degree \(3\) leaves paths and cycles), in time \(2^{N_0+3}n^{O(1)}\) and polynomial space. The multiplier reduction is applied only to parts with at most \(K_0\) vertices of degree \(3\); such a part with its cut vertex has pathwidth at most \(K_0+3\), so the reduction takes polynomial time. An instance is a graph \(G\) with \(\Delta(G)\le3\) and a cardinality function, and either no separation (a fresh instance) or a separation \((L,S,R)\) with \(S\subseteq V_3\) (a separated instance). The input is fresh. The algorithm applies the first rule that applies; for a fresh instance:

(F1)  if \(\Delta(G)\le2\) or \(n_3\le N_0\), count directly;

(F2)  if \(G\) is disconnected, solve its components as fresh instances and multiply the results;

(F3)  apply the multiplier reduction;

(F4)  if \(G\) has a \((3,3,3)\) vertex \(x\) (chosen as by Gaspers and Lee): if exactly two skeleton edges join \(N(x)\) to vertices outside \(N[x]\), with far ends \(y\) and \(z\), branch on \(y\), and in each branch fold what remains of the part cut off by \(\{y,z\}\) that contains \(x\) into \(z\) by the multiplier reduction (or count it directly if it has become a component); otherwise branch on \(x\);

(F5)  otherwise compute a separation by Lemma C.2(b) with \(\mu_r(X)=r_3|X\cap V_3|\), which is \(r_3\)-Lipschitz, and continue with the separated instance.

For a separated instance, with the sides named so that \(a\ge b\):

(S1)  if \(\Delta(G)\le2\) or \(n_3\le N_0\), count directly;

(S2)  if \(S=\emptyset\), solve the components of \(G\) as fresh instances and multiply the results;

(S3)  if some component of \(G\) has at most \(N_0\) vertices of degree \(3\), count it directly and delete it;

(S4)  apply the multiplier reduction;

(S5)  (move) if some \(v\in S\) has \(e_L(v)=0\), move \(v\) into \(R\), together with the inner vertices of its \(2\)-paths that lie in \(L\); symmetrically if \(e_R(v)=0\);

(S6)  (pull) if \(t>2B-J\) and some \(v\in S\) has \(e_L(v)>e_R(v)\), let \(q\) be the far end of the skeleton edge at \(v\) that ends in \(R\); move \(v\) and the inner vertices of that skeleton edge into \(L\), and \(q\) into \(S\);

(S7)  otherwise branch on any \(v\in S\), keeping the separation restricted to the remaining vertices.

In (F2) and (S2), components with at most \(N_0\) vertices of degree \(3\) are counted directly. Every step that deletes vertices is followed, as part of the same step, by a clean-up: vertices of degree \(1\) are folded into their neighbors by the multiplier reduction and vertices of degree \(0\) are counted, as long as there are any; then, in a separated instance, the separator is normalized:

(N)  while some \(u\in S\) has degree \(2\), let \(P\) be the maximal path or cycle through \(u\) whose inner vertices have degree \(2\), with ends \(f_1,f_2\in V_3\) if it is a path; if no end lies in \(R\), move the inner vertices of \(P\) into \(L\); else, if no end lies in \(L\), move them into \(R\); else, say \(f_1\in L\) and \(f_2\in R\), move them into \(L\) and \(f_2\) into \(S\).

Each operation of (N) gives a separation and lowers the number of vertices of degree \(2\) in \(S\), so afterwards \(S\subseteq V_3\). Every rule computes the weighted count exactly; the separation only steers the choice of vertices.

Lemma C.7 (moves and deletions).  Let \(s_3>r_3\), and let \(I'\) be obtained from a separated instance \(I\) by (S3), (S4), (S5) or (S6), including the clean-up. Then \(\mu_{\mathrm{sep}}(I')\le\mu_{\mathrm{sep}}(I)\), and the argument \(\max\{a,b\}+s_3|S|\) of \(\Lambda\) does not increase.

Proof. (S3), (S4) and the removal of vertices of degree at most \(1\) delete vertices and lower degrees, so none of \(a\), \(b\), \(|S|\) increases. An operation of (N) moves vertices of weight \(0\) and either lowers \(|S|\) or keeps \(|S|\) and lowers \(a\) by \(r_3\). In (S5) with \(e_L(v)=0\), the result is a separation, \(|S|\) drops by one, \(a\) grows by \(r_3\) and \(b\) is unchanged; by (C.6) \(\Xi\) grows by at most \(r_3\), and the argument of \(\Lambda\) changes by at most \(r_3-s_3<0\). In (S6), \(e_R(v)\ge1\) and \(e_L(v)\ge2\) force \((e_L,e_R,e_S)(v)=(2,1,0)\), so \(q\) is unique and the result is a separation; \(|S|\) is unchanged, \(a'=a-r_3\), \(b'=b+r_3\) and \(a'-b'=t-2r_3>2B-J-2r_3>0\). So the piece \(b\) is not active at \((a',b')\), and by (C.6) \(\Xi\) does not increase; the argument of \(\Lambda\) drops by \(r_3\).  ∎

For \(G\) with \(\Delta(G)\le3\) and \(\delta(G)\ge2\), the closure of \(X_0\subseteq V_3\) is the smallest \(Z\supseteq X_0\) that contains every vertex of \(V_3\) joined to \(Z\) by at least two skeleton edges. Let \(\partial Z\) be the set of skeleton edges with exactly one end in \(Z\), and \(Y\) the set of vertices of \(V_3\setminus Z\) joined to \(Z\) by exactly one skeleton edge.

Lemma C.8 (the clean-up after a deletion).  Let \(\Delta(G)\le3\), \(\delta(G)\ge2\), let \(\emptyset\ne X_0\subseteq V_3\) have closure \(Z\), and let \(G'\) be obtained from \(G\) by deleting \(X_0\) and some neighbors of degree \(2\) of vertices of \(X_0\), and then removing vertices of degree at most \(1\) as long as there are any. Then \(G'\) is \(G\) minus \(Z\) and the inner vertices of the skeleton edges with an end in \(Z\); in \(G'\) the vertices of \(Y\) have degree \(2\) and those of \(V_3\setminus(Z\cup Y)\) degree \(3\). Moreover \(|Y|=|\partial Z|\le|\partial X_0|\), \(|Z|\le|X_0|+|\partial X_0|\), and \(\partial Z\ne\emptyset\) if some component of the skeleton that meets \(X_0\) has more than \(|X_0|+|\partial X_0|\) vertices.

Proof. Let \(W\) be \(Z\) with the inner vertices of the skeleton edges at \(Z\). The removals leave the largest subgraph of minimum degree at least \(2\), whatever their order. In \(G-W\) a vertex of \(V_3\setminus Z\) has lost one edge per skeleton edge to \(Z\), so it has degree \(2\) if it is in \(Y\) and \(3\) otherwise; all deleted vertices lie in \(W\), so no vertex outside \(W\) is removed. Conversely, \(Z\) arises from \(X_0\) by adding, one at a time, vertices joined to the current set by two or more skeleton edges; once the current set is gone, the inner vertices of its skeleton edges are removed one after another, and then the next added vertex has degree at most \(1\). So all of \(W\) disappears. Adding a vertex joined to the set by \(k\ge2\) skeleton edges changes the number of leaving skeleton edges by \((3-k)-k\le-1\), so \(|Y|=|\partial Z|\le|\partial X_0|-|Z\setminus X_0|\). If \(\partial Z=\emptyset\), then \(Z\) contains every component of the skeleton that meets \(X_0\).  ∎

Lemma C.9 (branchings).  Let \(N_0\ge17\), \(s_3+\frac32r_3\ge1\), \(2s_3\ge1\) and \(s_3\ge\frac{r_3}2\). Let \(I\) be a separated instance to which none of (S1)–(S6) applies, and let \(I'\) be either branch of (S7), including the clean-up. Then \(\mu_{\mathrm{sep}}(I')\le\mu_{\mathrm{sep}}(I)-1\), and the argument of \(\Lambda\) does not increase.

Proof. Let \(v\in S\) be the branching vertex. As (S1)–(S4) do not apply, \(\delta(G)\ge2\), every component of \(G\) meeting \(V_3\) has more than \(N_0\ge17\) vertices of degree \(3\), and the skeleton has no loop; as (S5) does not apply, \(e_L(v),e_R(v)\ge1\). Let \(X_0=\{v\}\) in the branch \(G-v\), and let \(X_0\) be \(v\) with its neighbors of degree \(3\) in the branch \(G-N[v]\). With \(Z,Y\) as in Lemma C.8, \(|\partial X_0|\le12\), so \(|Y|\le12\), \(|Z|\le16\) and \(\partial Z\ne\emptyset\).

We have \(|Z\setminus\{v\}|+|Y|\ge3\): if \(Z=\{v\}\), the three skeleton neighbors of \(v\) are distinct and form \(Y\); if \(Z=\{v,u\}\), at most two skeleton edges join \(v\) and \(u\), so \(|\partial Z|\ge2\); if \(|Z|\ge3\), use \(|Y|\ge1\). After the clean-up the vertices of degree \(2\) in \(S\) are those of \(Y\cap S\). Each path or cycle \(P\) of (N) through \(k\ge1\) of them takes these \(k\) vertices out of \(S\) and puts at most one end \(f\in R\) into \(S\); each such \(f\) serves one \(P\) only. Give a credit to every vertex of \((Z\setminus\{v\})\cup Y\): an \(a\)-credit if it lies in \(R\), a \(b\)-credit if it lies in \(L\), an \(s\)-credit if it lies in \((Z\cap S)\setminus\{v\}\); on each \(P\), \(k-1\) of its vertices of \(Y\cap S\) get an \(s\)-credit and the last gets an \(a\)-credit (for \(f\)) if an end enters \(S\) and an \(s\)-credit otherwise. With \(\#_a,\#_b,\#_s\) the numbers of credits, \(\#_a+\#_b+\#_s\ge3\), and, as no vertex of degree \(3\) enters \(L\) or \(R\), \[|S'|\le|S|-1-\#_s,\qquad a'\le a-r_3\#_a,\qquad b'\le b-r_3\#_b .\] So the argument of \(\Lambda\) does not increase, and the imbalance changes by at most \(r_3(|Z|+2|Y|)\le40r_3=J\).

If \(t\le2B-J\), then \(|a'-b'|\le2B\), \(\Xi=\frac{a+b}2+B\) before and after, and the measure drops by at least \(s_3(1+\#_s)+\frac{r_3}2(\#_a+\#_b)\ge s_3+\frac32r_3\ge1\). If \(t>2B-J\), then, as (S6) does not apply, \((e_R,e_L,e_S)(v)\) is \((2,1,0)\) or \((1,1,1)\). We claim \(\#_s\ge1\) or \(\#_a\ge2\). Suppose \(\#_s=0\); then \(Z\cap S=\{v\}\) and every vertex of \(Y\cap S\) has an \(a\)-credit, so every skeleton edge from \(Z_R\cup\{v\}\), where \(Z_R=Z\cap R\), to a vertex of \((R\cup S)\setminus Z\) yields its own \(a\)-credit. If \(Z_R=\emptyset\), the \(e_R(v)\) edges into \(R\) give \(e_R(v)\) credits, and if \(e_R(v)=1\) the skeleton neighbor of \(v\) in \(S\) gives another. If \(|Z_R|\ge2\) we are done. If \(Z_R=\{z\}\), at most two of the three skeleton edges at \(z\) go to \(v\), and the others end in \((R\cup S)\setminus Z\). Now if \(\#_s\ge1\), \(|S|\) drops by two and the measure by \(2s_3\ge1\). Otherwise \(\#_a\ge2\), \(\#_a+\#_b\ge3\) and \(a'-b'\ge t-J>2B-2J>0\), so \(b\) is not active after the step and, by (C.6), \(\Xi\) drops by at least \(\min\{2r_3,\frac32r_3\}\); the measure drops by at least \(s_3+\frac32r_3\ge1\).  ∎

Lemma C.10 (initial measure).  Let \(c\in(c_{3},\frac13)\), \(s_3\ge\frac{r_3}2\), \(\kappa=c\,s_3+\frac{1-c}2r_3\) and \(\kappa<r_3\). There are \(N'_0\) and \(\eta'>0\) such that for every \(\eta>0\) and every connected \(G\) with \(\Delta(G)\le3\), \(\delta(G)\ge2\) and \(n_3\ge N'_0\), the separation of (F5) satisfies \(\mu_{\mathrm{sep}}(L,S,R)\le\kappa n_3+2B+\Lambda\bigl(r_3n_3/(1+\eta')\bigr)\), and the argument of \(\Lambda\) in it is at most \(r_3n_3/(1+\eta')\).

Proof. By Lemma C.2(b), \(k=|S|\le c_{3}n_3+\rho_3(n_3)\le cn_3\) for large \(n_3\), \(|a-b|\le r_3\) and \(a+b=r_3(n_3-k)\). As \(\max\{a,b\}=\frac{a+b}2+\frac{|a-b|}2\), both \(s_3k+\Xi(a,b)-B\) and \(\max\{a,b\}+s_3k\) are at most \(s_3k+\frac{r_3(n_3-k)}2+\frac{r_3}2\), which is nondecreasing in \(k\); so the first is at most \(\kappa n_3+B\) (as \(\frac{r_3}2<B\)), and the second at most \(\kappa n_3+\frac{r_3}2\le r_3n_3/(1+\eta')\) for a suitable \(\eta'\) and large \(n_3\), as \(\kappa<r_3\). The bound on the measure follows as \(\Lambda\) is nondecreasing.  ∎

Measures of all instances.

Graphs with a \((3,3,3)\) vertex are measured with weights \(w'_2,w'_3\) for the vertices of degree \(2\) and \(3\), as in (Gaspers and Lee 2023 Lemma 5). Let \(\ell(G)=w'_2n_2+w'_3n_3\), \(m(G)=\min\{\ell(G),\kappa n_3\}\), and let \(\eta'\) be as in Lemma C.10. The measure \(\mu(I)\) of an instance \(I\) on \(G\) is \(0\) if \(\Delta(G)\le2\) or \(n_3\le N_0\); otherwise it is \(\mu_3(G)=\ell(G)+\Lambda(r_3n_3)\) for a fresh instance with a \((3,3,3)\) vertex, \(\mu_f(G)=m(G)+2B+\Lambda\bigl(r_3n_3/(1+\eta')\bigr)\) for a fresh instance without one, and \(\mu_{\mathrm{sep}}(L,S,R)\) for a separated instance.

Table 10: The constraints of the subcubic analysis and their values at the weights (C.7), with \(c=0.13985\) and \(\kappa=c\,s_3+\frac{1-c}2r_3\). Linear constraints read “expression \(\ge0\)” and are checked exactly; for the branching vectors \((a,b)\) the last column is an upper bound on \(2^{-a}+2^{-b}\) in interval arithmetic. Decimals are rounded.

No.	Origin	Expression	\(\text{value}\)
(U1)	Lemma C.9	\(s_3+\frac32r_3-1\)	\(0\)
(U2)	Lemmas C.7 and C.9	\(s_3-r_3\); \(2s_3-1\)	\(0.5516;\ 0.4619\)
(U3)	Lemma C.10, (C.3)	\(r_3-\kappa\)	\(1.108\cdot10^{-7}\)
(U4)	hand-over (F5)	\(w'_2\); \(2w'_3+w'_2-2\kappa\)	\(0.0052;\ 4.22\cdot10^{-7}\)
(B11)	(F4), branch on \(x\)	\((4w'_3-3w'_2,\ 8w'_3-4w'_2)\)	\(0.9999956\)
(B12)	(F4), branch on \(y\)	\((6w'_3-w'_2,\ 6w'_3-w'_2)\)	\(0.9623865\)

Weights and constants.

Let \(c=0.13985\), so \(c_{3}<0.1398222<c<\frac13\), and \[\begin{equation*} \tag{C.7} r_3=0.179364,\quad s_3=0.730954=1-\tfrac32r_3,\qquad w'_2=0.0052182,\quad w'_3=0.176755 , \end{equation*}\] exact decimals. They satisfy the constraints of Table 10, checked by is3_uniform_repair.py (part 1); in particular \(w'_2\le w'_3\) and \(\kappa<r_3\). Let \(N'_0,\eta'\) be as in Lemma C.10. We fix \(\eta>0\) with \((1+B)\log_{1+\eta}(1+\eta')\ge2B+1\), and \(N_0\ge\max\{N'_0,17\}\) with \(w'_3N_0\ge1\), \(\kappa N_0\ge1\) and \(r_3N_0\ge1+\eta'\). Then every graph with \(n_3>N_0\) satisfies \[\begin{equation*} \tag{C.8} \mu_f(G)\le\mu_3(G)-1, \end{equation*}\] as \(m\le\ell\) and \(\Lambda(r_3n_3/(1+\eta'))=\Lambda(r_3n_3)-(1+B)\log_{1+\eta}(1+\eta')\). For reals \(x_1,\dots,x_p\ge1\), induction on \(2^{x+y}-2^x-2^y=(2^x-1)(2^y-1)-1\ge0\) gives \[\begin{equation*} \tag{C.9} \textstyle\sum_{j=1}^p2^{x_j}\le2^{x_1+\dots+x_p}. \end{equation*}\]

Proof of Theorem C.6(a). We apply Lemma C.1 with \(\lambda=2\), no subroutine, the measure \(\mu\) and the secondary measure \(\nu\) defined below, and check its condition rule by rule. (F1), (S1) and the direct counts make no recursive call. (S3)–(S6): Lemma C.7. (F3) deletes vertices and lowers degrees; as \(0\le w'_2\le w'_3\), neither \(\ell\) nor \(n_3\) grows, no \((3,3,3)\) vertex appears, and if the \((3,3,3)\) vertices disappear the measure changes from \(\mu_3\) to \(\mu_f\le\mu_3-1\). (S7): Lemma C.9, with the vector \((1,1)\).

(F2): let \(C_1,\dots,C_p\) be the components with more than \(N_0\) vertices of degree \(3\). If \(G\) has a \((3,3,3)\) vertex, \(\mu(C_j)\le\ell(C_j)+\Lambda(r_3n_3(G))\) by (C.8) and \(\sum_j\ell(C_j)\le\ell(G)\). Otherwise \(\mu(C_j)\le m(C_j)+2B+\Lambda(r_3n_3(G)/(1+\eta'))\) and \(\sum_jm(C_j)\le m(G)\). As \(\ell(C_j)\ge m(C_j)\ge1\), (C.9) gives \(\sum_j2^{\mu(C_j)}\le2^{\mu(G)}\).

(F4): \(G\) is connected with \(n_3>N_0\) and \(\delta(G)\ge2\), its skeleton has no loop, the new instances are fresh with measure at most \(\ell+\Lambda(r_3n_3(G))\) by (C.8), so it suffices that \(\ell\) drops by the components of (B11) or (B12). Let \(e\) be the number of skeleton edges inside \(N(x)\); then \(6-2e\) skeleton edges leave \(N[x]\), and \(e=3\) would make \(n_3=4\). If \(6-2e\ge4\) we branch on \(x\). In \(G-x\), \(\ell\) drops by \(4w'_3-3w'_2\). In \(G-N[x]\) let \(Z,Y\) be as in Lemma C.8 for \(X_0=N[x]\); as \(n_3>17>|X_0|+|\partial X_0|\), \(\ell\) drops by at least \(|Z|w'_3+|Y|(w'_3-w'_2)\) with \(|Z|\ge4\) and \(|Y|\ge1\), which is at least \(8w'_3-4w'_2\) if \(|Z|+|Y|\ge8\). If \(Z=N[x]\), then \(|Y|=6-2e\ge4\). Otherwise \(|Z|\ge5\) and \(|Y|=|\partial Z|\equiv3|Z|\pmod2\), so \(|Z|+|Y|\ge8\) unless \(|Z|=5\), \(|Y|=1\); then the vertex of \(Y\) cuts off a part with five vertices of degree \(3\), and (F3) would apply as \(K_0\ge5\). If \(6-2e=2\), let \(H\) be \(N[x]\) with the inner vertices of the skeleton edges at \(N(x)\); it has four vertices of degree \(3\), and all edges leaving \(H\) end in \(y\) or \(z\). If \(y=z\), (F3) would apply at \(y\); so \(y\ne z\) and \(d(y)=d(z)=3\). In both branches \(y\) and the four vertices of degree \(3\) of \(H\) are deleted and \(z\) loses an edge or is deleted, so \(\ell\) drops by at least \(5w'_3+(w'_3-w'_2)\), which is (B12).

(F5): \(G\) is connected, \(\delta(G)\ge2\), \(n_3>N_0\ge N'_0\), and every vertex of degree \(3\) has a neighbor of degree \(2\), so \(n_3\le2n_2\). If \(w'_3\ge\kappa\), then \(\ell(G)\ge\kappa n_3\); otherwise \(\ell(G)-\kappa n_3\ge(\frac{w'_2}2+w'_3-\kappa)n_3\ge0\) by (U4). So \(m(G)=\kappa n_3\), and Lemma C.10 gives \(\mu(I')\le\mu_f(G)\).

(S2): let the instance be \((L,\emptyset,R)\) with \(a\ge b\), so \(\mu\ge a+\Lambda(a)\). A component \(C\) with \(n_3(C)>N_0\) lies in \(L\) or in \(R\), has no \((3,3,3)\) vertex, and \(1+\eta'\le r_3n_3(C)\le a\); by \(\kappa<r_3\) and the choice of \(\eta\), \[\mu(C)\le\kappa n_3(C)+2B+\Lambda(r_3n_3(C))-(1+B)\log_{1+\eta}(1+\eta')\le r_3n_3(C)+\Lambda(a)-1 .\] As \(\sum_{C\subseteq R}r_3n_3(C)\le a\) and \(\sum_{C\subseteq L}r_3n_3(C)\le b\le a\), (C.9) gives \(\sum_C2^{\mu(C)}\le2^{\Lambda(a)-1}(2^a+2^b)\le2^\mu\). If \(G\) is connected, the new instance is \(G\) itself, with measure at most \(\mu-1\).

Secondary measure. For an instance on a graph with \(n\) vertices and \(m\) edges let \(p=n+m\), \(T=3(n+1)^2\), \(M=\lfloor n+2B+\Lambda(n)\rfloor\ge\lfloor\mu\rfloor\) (as \(s_3+r_3<1\) and \(w'_3<1\)), \(\tau=(2n+2)|S|+|a-b|/r_3<T\) for a separated and \(\tau=T\) for a fresh instance, and \(\nu=(M+1)(T+1)p+(T+1)\lfloor\mu\rfloor+\tau\). A step that deletes a vertex or an edge lowers \(p\) and so \(\nu\). Of the steps that keep the graph, none raises \(\mu\); (F5) lowers \(\tau\) from \(T\); (S2) on a connected graph lowers \(\lfloor\mu\rfloor\) and raises \(\tau\) by at most \(T\); (S5) lowers \(\tau\) by at least \(2n+1\), and (S6) by \(2\). So \(\nu\) drops in every step, and the rules terminate.

Conclusion. The input has \(\mu\le\mu_3(G)\le w'_3n+\Lambda(n)\). By Lemma C.1 the running time is \(2^{w'_3n}n^{O(1)}\), and \(2^{0.176755}<1.130339\). Every step takes polynomial time and space, and the recursion depth is at most the initial \(\nu\), so the space is polynomial.  ∎

C.7 Maximum degree at least 4

The algorithm.

On graphs of maximum degree at most \(3\) the algorithm is that of Appendix C.6. Fix constants \(K\ge65\), \(K_m\ge6K+1\) and \(N_1=7K+2\). In a graph of maximum degree at least \(4\) the algorithm splits a disconnected graph into its components, solves every component with at most \(N_1\) vertices directly in constant time, and otherwise selects a vertex \(x\) of maximum degree: as by Gaspers and Lee if \(\Delta(G)=4\) or the component is regular, and otherwise, if \(\Delta(G)\ge5\), a vertex of maximum degree with a neighbor of smaller degree (one exists in every connected non-regular graph). It then applies the first of the following rules that applies.

• Multiplier reduction at a cut vertex \(v\) such that some component of \(G-v\) has at most \(K_m\) vertices.

• Hybrid rule, if \(x\) has a lazy \(2\)-separator: distinct vertices \(y,z\) with \(d(y),d(z)\ge3\) such that \(G-\{y,z\}\) is disconnected and \(N[x]\setminus\{y,z\}\) lies in one component of \(G-\{y,z\}\) with at most \(K\) vertices (\(x\) may belong to the pair). For each \(v\in\{y,z,x\}\) in this order it computes the two instances of the branching on \(v\), and it branches on the first \(v\) whose instances \(I_1,I_2\) satisfy \(2^{\mu(I_1)}+2^{\mu(I_2)}\le2^{\mu(G)}\) for the measures below without their sublinear term \(\Lambda\), and on \(y\) if there is none. The weights are rational, so this is a polynomial-time test in exact arithmetic. As \(\Lambda(I_j)\le\Lambda(G)\), a branching that passes the test satisfies the same inequality for the full measures.

• Otherwise branch on \(x\).

The instances of a branching on \(v\) are \(G-v\) and \(G-N[v]\), each taken after the reductions that make no recursive call, applied as long as one applies: the removal of vertices of degree at most \(1\), the multiplier reduction, and the direct solution of components with at most \(N_1\) vertices. Our lazy \(2\)-separator is a reading of the rule of Gaspers and Lee (Gaspers and Lee 2023 Algorithm #IS), which branches on \(y\). Proposition C.26 below shows that under this reading their branching alone can violate the condition of Lemma C.1.

The measures.

We follow (Gaspers and Lee 2023 Lemmas 6 and 8, Theorem 1). All measures have the form \(\sum_iw_in_i\) with \(w_0=w_1=0\), plus, for maximum degree at least \(4\), the sublinear term \(\Lambda(r_3|V(G)|)\), which no step increases and which is at least the term \(\Lambda(r_3n_3)\) of \(\mu_3\) of every graph of maximum degree at most \(3\) that arises from \(G\); we omit it below. We write \(\Delta w_i=w_i-w_{i-1}\). From now on a \(2\)-path is a path of length at least \(2\) whose inner vertices have degree \(2\) and whose ends have degree at least \(3\); its far end from one end is the other.

Maximum degree \(4\). The pivots \(p_2,\dots,p_5=3,\frac{16}5,\frac72,\frac{15}4\) cut the interval \([2,4]\) of average degrees \(d(G)=2|E(G)|/|V(G)|\) into five sections. Section \(1\), \([2,3]\), has the weights \((w^{(1)}_2,w^{(1)}_3)=(w'_2,w'_3)\) of (C.7) and a weight \(w^{(1)}_4\), and its measure \(\mu^{(1)}\) has the additional term \(\psi\cdot\mathrm{ind}(G)\), where \(\psi\ge0\) and \(\mathrm{ind}(G)=1\) if all degrees of \(G\) are \(2\) or \(4\) and no two vertices of degree \(4\) are adjacent, and \(\mathrm{ind}(G)=0\) otherwise. Section \(k\ge2\) has \(w^{(k)}_i=w^{(k-1)}_i-(i-p_k)\alpha_k\) (\(i=2,3,4\)) with \(\alpha_k\ge0\), so that \[\begin{equation*} \tag{C.10} \mu^{(k)}_{\mathrm{lin}}(G)-\mu^{(k-1)}_{\mathrm{lin}}(G)=-\alpha_k|V(G)|\,(d(G)-p_k), \end{equation*}\] where \(\mu^{(k)}_{\mathrm{lin}}=\sum_iw^{(k)}_in_i\) and \(\mu^{(k)}=\mu^{(k)}_{\mathrm{lin}}\) for \(k\ge2\). A graph \(G\) of maximum degree \(4\) has the measure \(\mu_4(G)=\min_k\mu^{(k)}(G)\), and its minimizing section is the smallest \(k\) with \(\mu^{(k)}(G)=\mu_4(G)\). Let \(\tau_k\) be the maximum of \(\sum_ix_iw^{(k)}_i\) over the degree distributions \(x\) on \(\{2,3,4\}\) with average degree in section \(k\). The degree-\(4\) branchings are those of (Gaspers and Lee 2023 Table 1), listed by the degrees of the neighbors of \(x\) (the type of \(x\)), each with a branching vector and a highest average degree \(h\), the largest \(d(G)\) of a graph in which the selection rule can pick a vertex of this type (Wahlström’s averaging argument (Wahlström 2008), which we use as Gaspers and Lee do). Its group is the section that contains \(h\), the lower of the two sections if \(h\) is a common end of two sections. Two entries of that table are misprinted (as in Figure 4 of (Gaspers and Lee 2016)): the first component for type \((2,2,2,3)\) is \(4w_4-2w_3+2w_2\), and in cases (a) and (b) of type \((2,2,2,2)\) both components are \(5w_4-4w_3+4w_2+\psi\) and \(4w_4-2w_3+3w_2-\psi\), respectively (the signs of \(\psi\) are swapped in print). Case (a) is a vertex of type \((2,2,2,2)\) all of whose \(2\)-paths end at vertices of degree \(4\); case (b) has a \(2\)-path to a vertex of degree \(3\).

Degrees \(5\) and \(6\). One measure \(\sum_iw_in_i\) with weights \(w_2,\dots,w_6\), at least those of section \(5\) on degrees \(2,3,4\), increasing and concave. Branching on a vertex \(v\) with \(d(v)\in\{5,6\}\) has the vector (Gaspers and Lee 2023 Lemma 8) \[\begin{equation*} \tag{C.11} \Bigl(w_{d(v)}+\sum_{u\in N(v)}w_{d(u)}+\mathrm{out}(v)\,\Delta w_{d(v)},\ \ w_{d(v)}+\sum_{u\in N(v)}\Delta w_{d(u)}+\deg_2(v)\,\Delta w_{d(v)}\Bigr), \end{equation*}\] where \(\deg_2(v)\) is the number of neighbors of degree \(2\), \(\mathrm{out}(v)=5\) for the neighbor degrees \((2,2,2,2,2)\) and \((2,2,2,2,2,3)\), \(\mathrm{out}(v)=6\) for \((2,\dots,2)\) with \(d(v)=6\), and otherwise \(\mathrm{out}(v)=3\) if \(\sum_{u\in N(v)}d(u)-d(v)\) is odd and \(4\) if it is even.

Degree at least \(7\). The measure is \(w_6|V(G)|\); a branching deletes one vertex or at least eight.

Cross-section cases.

A type with highest average degree \(h\) can be selected in every graph with \(d(G)\le h\). By (C.10), a graph whose average degree lies inside section \(k\) has minimizing section \(k\), and a graph with \(d(G)=p_k\) has minimizing section at most \(k-1\). So in a graph with minimizing section \(k\) the selection rule picks only types whose group is at least \(k\); we call these types admissible for section \(k\), and we check the vector of every type under the weights of its own section and of every earlier section. A graph with \(\mathrm{ind}(G)=1\) has \(4n_4\le2n_2\), so \(d(G)\le\frac83\), and its minimizing section is \(1\), since \(\mu^{(2)}-\mu^{(1)}\ge\alpha_2|V(G)|(3-d(G))-\psi\ge\frac{\alpha_2}3-\psi>0\) for our weights.

The potential.

The printed vectors account for \(\mathrm{ind}\) only in cases (a) and (b). Case (a) is selected only when every vertex of degree \(4\) has type \((2,2,2,2)\), the type of smallest associated average degree, and no vertex has degree \(3\) (otherwise #IS would branch on a case-(b) vertex), so \(\mathrm{ind}(G)=1\); case (b) occurs only when \(\mathrm{ind}(G)=0\). Other section-\(1\) branchings may switch the indicator from \(0\) to \(1\). The indicator is evaluated after the removal of vertices of degree at most \(1\); each further reduction in the definition of the instances deletes at least two vertices of degree at least \(2\), so it lowers the linear part of \(\mu^{(1)}\) by at least \(2w^{(1)}_2=0.0104364>\psi\), and no \(\mu^{(k)}\) increases even if the indicator switches. Subtracting \(\psi\) from both components keeps every section-\(1\) vector other than (a), (b) and \((2,2,2,3)\) valid (sums at most \(0.90706\)), and every later-group vector under section-\(1\) weights (sums at most \(0.89110\)). For \((2,2,2,3)\), Lemma C.11 gives the excess \(\varepsilon=(w^{(1)}_3-w^{(1)}_2)-(w^{(1)}_4-w^{(1)}_3)=0.0122914>\psi\) in each branch where the indicator switches; with \(\varepsilon-\psi\) added in the first, the second or both components, the sums are at most \(0.99543\), \(0.99544\) and \(0.99331\). These checks are part 2 of gaspers_lee_general_uniform.py.

In the next lemma \(w_i=w^{(1)}_i\), the instance \(G'\) of a branch is taken after the removal of vertices of degree at most \(1\), and the printed component of a branch is the corresponding component of the vector of \((2,2,2,3)\) in (Gaspers and Lee 2023 Table 1). The decrease \(\sum_v(w_{d_G(v)}-w_{d_{G'}(v)})\), with \(w_0=w_1=0\) and deleted vertices of degree \(0\), is a sum of nonnegative terms.

Lemma C.11 (the potential in case \((2,2,2,3)\)).  Let \(G\) be a connected graph with more than \(N_1\) vertices, minimizing section \(1\), \(\Delta(G)\le4\) and \(\delta(G)\ge2\), to which neither the multiplier reduction nor the hybrid rule applies, and let \(x\) have type \((2,2,2,3)\). If the instance \(G'\) of a branch on \(x\) has indicator \(1\), its decrease exceeds the printed component by at least \(\varepsilon\).

Proof. Let \(u\) be the neighbor of degree \(3\) of \(x\), \(y_1,y_2,y_3\) the others, and \(t_i\) the far end of the \(2\)-path that starts with \(xy_i\). The printed components charge \(w_4\) to \(x\), \(w_2\) to each \(y_i\), \(w_4-w_3\) to each \(t_i\) (the least drop of a vertex of degree at least \(3\) that loses an edge, as \(w_4-w_3<w_3-w_2\)), and \(w_3-w_2\) (branch \(G-x\)) or \(w_3\) (branch \(G-N[x]\)) to \(u\). In \(G'\) no vertex has degree \(3\).

Closed parts. Call \(P\supseteq\{x,y_1,y_2,y_3\}\) closed if it consists otherwise of vertices of degree \(3\) and inner vertices of \(2\)-paths, and deleting \(x\) and then removing vertices of degree at most \(1\) removes all of \(P\). Below, \(P\) is a component of \(G\) minus at most two vertices, so \(|P|>b\) with \(b=K\), \(K_m\) or \(N_1\) (otherwise the hybrid rule, the multiplier reduction or the rule for small components would apply). Then \(P\) disappears in both branches, and the excess is at least \(\sum_{v\in P\setminus\{x,y_1,y_2,y_3,u\}}w_{d(v)}-3(w_4-w_3)\), which is at least \(387w_2-3(w_4-w_3)=1.5417072>\varepsilon\) if \(b\ge K_m\ge391\), and at least \(2w_3+60w_2-3(w_4-w_3)=0.1888658>\varepsilon\) if \(b=K\ge65\), \(u\notin P\) and \(P\) has two vertices of degree \(3\).

\(G\) has an even number of vertices of degree \(3\), so one, \(z\), besides \(u\); choose it with the largest number \(k\) of indices \(i\) with \(t_i=z\). The charges at \(z\) are \(k(w_4-w_3)\), and \(z\) is deleted or loses an edge. The printed vectors use the drop of one vertex to cover a charge at another only for a far end of degree \(3\) at which two \(2\)-paths end (the drop along its third skeleton edge), which is then \(z\) with \(k=2\), and when \(u\) is a far end, treated last. If \(k=3\), \(x\), \(z\) and the three \(2\)-paths form a closed part, a component of \(G-u\). If \(k=0\), \(z\) drops by at least \(w_3-w_2>\varepsilon\). If \(k=1\), \(z\) drops by \(w_3-w_2=(w_4-w_3)+\varepsilon\) or by \(w_3>(w_4-w_3)+\varepsilon\). If \(k=2\), \(z\) is deleted, and the far end \(z''\) of its third \(2\)-path loses an edge and has degree \(2\) or is deleted in \(G'\). If \(z''\) is not charged, the excess at \(z,z''\) is at least \(w_3+(w_3-w_2)-2(w_4-w_3)=0.0298010\). If \(z''\) is the third far end and \(d(z'')=4\), it is at least \(w_3+(w_4-w_2)-3(w_4-w_3)=0.0298010\). If \(z''\) is the third far end, \(d(z'')=3\) and \(f\) is the far end of its third \(2\)-path, then \(x,z,z''\) and the \(2\)-paths between them and to \(f\) form a closed part, a component of \(G-\{u,f\}\) (of \(G-u\) if \(f=u\)), with two vertices of degree \(3\). If \(z''=u\): in \(G-x\), \(u\) is deleted and the far end \(q\) of its third \(2\)-path loses an edge; in \(G-N[x]\) the drop at \(q\) is not charged; arguing for \(q\) as for \(z''\) (if \(q\) is the third far end and \(d(q)=3\), \(x,u,z\) and their \(2\)-paths form a closed part, a component of \(G-q\)), the excess at \(z,u,q\) is at least \(2w_3-2(w_4-w_3)=0.0350192\) in \(G-x\) and \(w_3+(w_3-w_2)-2(w_4-w_3)\) in \(G-N[x]\).

If \(u=t_i\), the printed vectors use the drop at the third skeleton neighbor \(q\) of \(u\) for the charges at \(u\). If \(z\ne q\), the cases above apply, with \(z''\ne q\) for \(k=2\) (otherwise \(x,u,z\) and their \(2\)-paths form a closed part, a component of \(G-q\)). If \(z=q\) and \(k=2\), then \(G\) is a closed part with \(b=N_1\). If \(z=q\) and \(k\le1\), the excess at \(u\) and \(z\) is at least \(w_3-(w_4-w_3)\) and \(\varepsilon\) in the two branches if \(k=0\), and \(2w_3-2(w_4-w_3)\) and \(w_3+(w_3-w_2)-2(w_4-w_3)\) if \(k=1\). The excesses of the cases \(k\le2\) and \(u=t_i\) are checked exactly in part 2 of gaspers_lee_general_uniform.py.  ∎

Regular neighborhoods.

The vectors (C.11) are not needed for the types \((5,5,5,5,5)\) and \((6,\dots,6)\): a vertex of maximum degree all of whose neighbors have this degree is selected only in a regular component. A \(\Delta\)-regular component with \(\Delta\in\{5,6,7\}\) arises at most once for each \(\Delta\) on a root-to-leaf path of the search tree, since degrees never increase and components are solved separately; so these branchings cost a constant factor in the running time.

Weights.

The polynomial-space algorithms use the weights of Table 11 and, for degrees \(5\) and \(6\), \[\begin{equation*} \tag{C.12} (w_2,\dots,w_6)=(0.1136655,\ 0.1986263,\ 0.2673669,\ 0.295498,\ 0.3034362). \end{equation*}\] The exponential-space algorithm of part (d) uses one measure for degrees \(5\) to \(7\), with \[\begin{equation*} \tag{C.13} (w_2,\dots,w_7)=(0.1103289,\ 0.1932144,\ 0.2500011,\ 0.2867833,\ 0.296828,\ 0.2970601), \end{equation*}\] and \(w_7|V(G)|\) for maximum degree at least \(8\). All decimals are exact.

Table 11: The weights of the five sections at maximum degree \(4\); section 1 also has \(\psi=0.0061458\). All decimals are exact, and \(\tau_k\) is computed exactly.

\(k\)	\(\text{section}\)	\(\alpha_k\)	\(w^{(k)}_2\)	\(w^{(k)}_3\)	\(w^{(k)}_4\)	\(\tau_k\)
1	\([2,3]\)	\(-\)	\(0.0052182\)	\(0.176755\)	\(0.3360004\)	\(0.176755\)
2	\([3,\frac{16}5]\)	\(0.0484291\)	\(0.0536473\)	\(0.176755\)	\(0.2875713\)	\(0.19891826\)
3	\([\frac{16}5,\frac72]\)	\(0.0142955\)	\(0.0708019\)	\(0.1796141\)	\(0.2761349\)	\(0.2278745\)
4	\([\frac72,\frac{15}4]\)	\(0.0122574\)	\(0.089188\)	\(0.1857428\)	\(0.2700062\)	\(0.24894035\)
5	\([\frac{15}4,4]\)	\(0.0105598\)	\(0.10766765\)	\(0.19366265\)	\(0.26736625\)	\(0.26736625\)

The analysis needs two steps that the paper of Gaspers and Lee does not prove: the vectors of their Lemma 8 rest on a bound on the number of edges leaving \(N[v]\) (their Lemma 7) stated for \(3\)-connected graphs, and the lazy \(2\)-separator branching has no analyzed vector. We prove them for our algorithm in Appendices C.8 and C.9.

Proposition C.12.  For the algorithm and the constants above, the following hold.

(G1)  Let \(v\) be a vertex of maximum degree \(d(v)\in\{5,6\}\) with the weights (C.12), or \(d(v)\in\{5,6,7\}\) with the weights (C.13), on which the algorithm branches other than in the hybrid rule. Then (C.11) is a branching vector of this branching for \(\sum_iw_in_i\), the instances being taken after the removal of vertices of degree at most \(1\).

(G2)  Every branching of the hybrid rule in a graph of maximum degree \(\Delta\ge4\) whose component, if \(\Delta\in\{5,6\}\), is not \(\Delta\)-regular, satisfies the condition of Lemma C.1 for the measures above.

Proof of Theorem C.6(b)–(d). (b), (c): we apply Lemma C.1 with \(\lambda=2\) to the algorithm above with the measures above. The following are checked by part 1 of gaspers_lee_general_uniform.py: every vector of (Gaspers and Lee 2023 Table 1), corrected as above, under the weights of its own section and of every earlier section (interval arithmetic; largest sums \(0.9999997\) and \(0.9671\)); every vector (C.11) for \(d(v)\in\{5,6\}\) and all neighbor degrees in \(\{2,\dots,d(v)\}\) except the regular neighborhoods (interval arithmetic); that the weights (C.12) are at least the section-\(5\) weights on degrees \(2,3,4\), increasing and concave, and that \(\alpha_k,\psi\ge0\) (exact); and the values \(\tau_k\), by exact enumeration of the vertices of the polytope of degree distributions with average degree in the section. By Lemma C.19 below and the paragraphs “Cross-section cases” and “The potential”, the degree-\(4\) branchings satisfy the condition of Lemma C.1, and the hand-overs between the measures are covered by Lemma C.19; so do those at degrees \(5\) and \(6\) by Proposition C.12(G1) and Lemma C.19, the reductions, which only delete vertices, and the branchings of the hybrid rule by Proposition C.12(G2), except in regular components, which cost a constant factor. For maximum degree at least \(7\), the measure \(w_6|V(G)|\) dominates \(\sum_iw_in_i\), and the vector \((w_6,8w_6)\) is valid because \(2^{w_6}>1.23408\) exceeds the positive root \(1.232055\ldots\) of \(\lambda^8=\lambda^7+1\). So graphs of maximum degree at most \(4\) are solved in time \(2^{\max_k\tau_kn}n^{O(1)}\) and \(2^{0.26736625}<1.203609\), and all graphs in time \(2^{w_6n}n^{O(1)}\) and \(2^{0.3034362}<1.234081\), in polynomial space.

For the chromatic number, Björklund, Husfeldt and Koivisto (Björklund, Husfeldt, and Koivisto 2009) show that \(G\) is \(k\)-colorable if and only if \(\sum_{X\subseteq V}(-1)^{|V\setminus X|}i(G[X])^k>0\), where \(i(H)\) is the number of independent sets of \(H\). Computing every \(i(G[X])\) in polynomial space takes time \(\sum_XO(1.2341^{|X|})=O(2.2341^n)\), and binary search over \(k\) adds a polynomial factor.

(d): if the current graph has maximum degree at most \(4\), compute a path decomposition of width \(\frac5{32}n_3+\frac14n_4+\rho(|V|)\) by Theorem 7.1(c) and Theorem 10.1(b), with \(|V|\) the number of vertices of the current graph, and count by the standard dynamic program in time \(2^{\frac5{32}n_3+\frac14n_4+\rho(|V|)}\mathop{\mathrm{poly}}(n)\). Above maximum degree \(4\) use the weights (C.13). They are at least \((0,\frac5{32},\frac14)\) on degrees \(2,3,4\), increasing and concave, and satisfy the vectors (C.11) for degrees \(5\) to \(7\) (largest sum \(0.9999990\), interval arithmetic; part 4 of gaspers_lee_general.py). These vectors are branching vectors by Proposition C.12(G1), and the hybrid rule is covered by Proposition C.12(G2), except in regular components. For maximum degree at least \(8\), \((w_7,9w_7)\) is valid since the positive root of \(\lambda^9=\lambda^8+1\) is below \(1.21315<2^{w_7}\). We apply Lemma C.1 with the dynamic program as the subroutine \(\mathcal B\) and the measures \(\mu+\rho(|V|)\) and \(\mu_{\mathcal B}+\rho(|V|)\), where \(\mu_{\mathcal B}=\frac5{32}n_3+\frac14n_4\le\mu\). No step increases \(|V|\) and \(\rho\) is nonnegative and nondecreasing (Theorem 10.1), so every branching condition for \(\mu\) remains valid. The time is \(2^{w_7n+\rho(n)}\mathop{\mathrm{poly}}(n)\), and \(2^{0.2970601}<1.228639\).  ∎

C.8 Proof of (G1)

Throughout Appendices C.8 and C.9, \(\mu(G)=\sum_{u\in V(G)}w_{d(u)}\) for weights \(w_0=w_1=0<w_2\le\dots\le w_D\), which are concave from \(2\) if \(\Delta w_2\ge\Delta w_3\ge\dots\ge\Delta w_D>0\). For \(X\subseteq V(G)\) let \(G\ominus X\) be the largest subgraph of \(G-X\) of minimum degree at least \(2\), which the removal of vertices of degree at most \(1\), in any order, leaves; let \(W(X)=V(G)\setminus(X\cup V(G\ominus X))\). For \(A,B\subseteq V(G)\), \(e(A,B)\) is the number of edges between \(A\) and \(B\), and \(e(A)\) the number inside \(A\).

Lemma C.13 (decrease of the measure).  Let \(X\subseteq V(G)\), \(G'=G\ominus X\) and \(W=W(X)\). Then \[\mu(G)-\mu(G')=\sum_{u\in X\cup W}w_{d(u)} +\sum_{s\in V(G')}\bigl(w_{d(s)}-w_{d_{G'}(s)}\bigr),\] with nonnegative terms, and \(2\le d_{G'}(s)\le d(s)-e(\{s\},X\cup W)\) for \(s\in V(G')\). If \(X\subseteq X'\), then \(\mu(G\ominus X')\le\mu(G\ominus X)\).

Proof. The identity sums the weights over \(X\), \(W\) and \(V(G')\); the terms are nonnegative as the weights are nondecreasing. \(G\ominus X'\) is a subgraph of \(G-X\) of minimum degree at least \(2\), hence of \(G\ominus X\).  ∎

Let \(\theta(v)=e(N[v],V(G)\setminus N[v])\). Counting edges at \(N(v)\), \[\begin{equation*} \tag{C.14} \textstyle\sum_{u\in N(v)}d(u)=d(v)+2e(N(v))+\theta(v), \end{equation*}\] so in (C.11) the parity cases have \(\theta(v)\equiv\mathrm{out}(v)\pmod 2\).

Lemma C.14 (the situation of a branching).  Let the algorithm branch on its selected vertex \(v\), other than in the hybrid rule, with \(5\le d(v)=\Delta(G)\le7\). Then \(G\) is connected, \(|V(G)|>N_1\), \(\delta(G)\ge2\), and:

(1)  if \(P\subseteq V(G)\setminus\{v\}\) is a nonempty union of components of \(G-v\) with \(|P|\le K_m\), then \(v\) has no neighbor outside \(P\); and if every edge leaving \(N[v]\) ends at one vertex \(c\), then \(c\) has no neighbor outside \(N[v]\);

(2)  there are no distinct \(y,z\notin N[v]\) with \(d(y),d(z)\ge3\) such that every edge leaving \(N[v]\) ends in \(\{y,z\}\) and \(G-\{y,z\}\) has a vertex outside \(N[v]\).

Proof. Small components are solved directly and vertices of degree at most \(1\) are removed. In (1), a neighbor of \(v\) outside \(P\), or of \(c\) outside \(N[v]\), would make \(v\) or \(c\) a cut vertex with a part of at most \(K_m\) vertices, and the multiplier reduction would apply. In (2), \(\{y,z\}\) would be a lazy \(2\)-separator for \(v\), as \(|N[v]|\le8\le K\).  ∎

Lemma C.15 (the branch \(G-v\)).  Let the weights be concave from \(2\) with \(w_2\ge2\Delta w_D\), and let \(G,v\) be as in Lemma C.14 with \(d(v)=D\). Then \(\mu(G)-\mu(G\ominus\{v\})\ge w_D+\sum_{u\in N(v)}\Delta w_{d(u)}+\deg_2(v)\Delta w_D\).

Proof. Use Lemma C.13 with \(X=\{v\}\). Let \(U_2\) and \(U_3\) be the neighbors of degree \(2\) and of degree at least \(3\). Each \(u\in U_2\) lies in \(W\) and contributes \(w_2=\Delta w_{d(u)}\); let \(t(u)\) be its other neighbor. By Lemma C.14(1), \(t(u)\notin U_2\). For \(s\ne v\) let \(m(s)=|\{u\in U_2:t(u)=s\}|\); it suffices that every \(s\) contributes at least \([s\in U_3]\Delta w_{d(s)}+m(s)\Delta w_D\). If \(s\) survives, it loses at least \([s\in U_3]+m(s)\) edges, and its term is a sum of that many increments \(\Delta w_i\) with \(3\le i\le d(s)\), the largest being \(\Delta w_{d(s)}\). If \(s\in W\), its term is \(w_{d(s)}\), and \(w_{d(s)}-\Delta w_{d(s)}\ge(d(s)-1)\Delta w_D\ge m(s)\Delta w_D\) for \(s\in U_3\), while \(w_{d(s)}\ge w_2+(d(s)-2)\Delta w_D\ge d(s)\Delta w_D\ge m(s)\Delta w_D\) otherwise.  ∎

Lemma C.16 (the branch \(G-N{[v]}\)).  Let the weights and \(G,v,D\) be as in Lemma C.15. Then \(\mu(G)-\mu(G\ominus N[v])\ge w_D+\sum_{u\in N(v)}w_{d(u)}+\mathrm{out}(v)\,\Delta w_D\).

Proof. Let \(X=N[v]\), \(W=W(X)\), \(\theta=\theta(v)\) and \(k_X(t)=e(\{t\},X)\). By Lemma C.13 the decrease is \(w_D+\sum_uw_{d(u)}+Q\), where, as every surviving \(s\) loses \(e(\{s\},X\cup W)\) edges and each edge leaving \(X\) ends in \(W\) or at a survivor, \[Q\ge\sum_{t\in W}w_{d(t)}+e(X\cup W,V(G\ominus X))\,\Delta w_D\ge \theta\,\Delta w_D+\sum_{t\in W}\bigl(w_{d(t)}-k_X(t)\Delta w_D\bigr),\] and every summand \(w_{d(t)}-k_X(t)\Delta w_D\) is at least \(w_2-2\Delta w_D\ge0\), and at least \(w_2-\Delta w_D\) if \(k_X(t)\le1\). We show \(Q\ge\mathrm{out}(v)\Delta w_D\). As \(|V(G)|>N_1\ge D+3\) and \(G\) is connected, \(\theta\ge1\).

\(\mathrm{out}(v)\in\{5,6\}\). By Lemma C.14(1) there is no edge inside the set \(U_2\) of neighbors of degree \(2\), and no two edges from \(U_2\) to a neighbor of degree \(3\). So \(e(N(v))=0\), or \(e(N(v))\le1\) for \((2,2,2,2,2,3)\), and (C.14) gives \(\theta\ge\mathrm{out}(v)\).

\(\mathrm{out}(v)\in\{3,4\}\). If \(\theta\ge\mathrm{out}(v)\) we are done; by parity, otherwise \((\theta,\mathrm{out}(v))\) is \((1,3)\) or \((2,4)\). If a leaving edge \(ab\) (\(a\in N(v)\)) has \(d(b)=2\), the vertices of degree \(2\) from \(b\) away from \(a\), \(b=t_1,\dots,t_p\), end at a vertex \(b'\) of degree at least \(3\); if no other leaving edge ends on this walk, then \(t_1,\dots,t_p\in W\). If \(\theta=1\), with leaving edge \(ab\), then \(d(b)=2\) by Lemma C.14(1), and \(Q\ge w_2+\Delta w_D\ge3\Delta w_D\) (\(b'\) is removed or loses an edge). If \(\theta=2\), with leaving edges \(a_1b_1\), \(a_2b_2\): if \(b_1=b_2=b\), then \(d(b)\ge3\) contradicts Lemma C.14(1), and \(d(b)=2\) makes \(X\cup\{b\}\) a component of \(D+2<|V(G)|\) vertices; if \(b_1\ne b_2\) have degree at least \(3\), Lemma C.14(2) is contradicted; if \(d(b_1)=d(b_2)=2\), then \(b_1,b_2\in W\) with \(k_X(b_i)=1\) and \(Q\ge2\Delta w_D+ 2(w_2-\Delta w_D)\ge4\Delta w_D\); if \(d(b_1)=2<d(b_2)\), the walk from \(b_1\) ends at \(b'\) (\(b'=b_2\) possible), and \(Q\ge pw_2+w_3\ge4\Delta w_D\) if \(b_2\in W\), \(Q\ge w_2+2\Delta w_D\) if \(b_2\notin W\) and \(b'=b_2\), and \(Q\ge w_2+\Delta w_D+\min\{w_3,\Delta w_D\}\) otherwise.  ∎

Proof of (G1). By Lemmas C.15 and C.16 it suffices that the weights are concave from \(2\) with \(w_2\ge2\Delta w_D\) for \(D=d(v)\). This is checked exactly by part A of g1_check.py: both weight vectors are increasing and concave from \(2\), \(w_2=0.1136655\ge4\Delta w_5\ge4\Delta w_6\) for (C.12), and \(w_2=0.1103289\ge2\Delta w_5=0.0735644\) with \(\Delta w_6,\Delta w_7<\Delta w_5\) for (C.13).  ∎

C.9 Proof of (G2)

A lazy configuration is the current graph \(G\) with \(\Delta=\Delta(G)\ge4\) when the hybrid rule applies, with the selected vertex \(x\) and its lazy \(2\)-separator \(\{y,z\}\), whose component \(C\supseteq N[x]\setminus\{y,z\}\) of \(G-\{y,z\}\) has \(|C|\le K\). Let \(C^+\) be the union of the components of \(G-\{y,z\}\) with at most \(K\) vertices, \(R=V(G)\setminus(C^+\cup\{y,z\})\), \(o_y=|N(y)\cap R|\), \(o_z=|N(z)\cap R|\), \(H=G[C^+\cup\{y,z\}]\) and \(\bar e=|C^+\setminus N[x]|\).

Lemma C.17 (the configuration).  In a lazy configuration, \(\delta(G)\ge2\); the neighbors of \(C^+\) lie in \(C^+\cup\{y,z\}\); every component of \(G[R]\) has more than \(K\) vertices; every component of \(G[C^+]\) contains a neighbor of \(y\) and one of \(z\); and \(|C^+|\le\Delta K\). If \(\Delta\le7\), then \(o_y,o_z\ge1\) and \(x\notin\{y,z\}\).

Proof. A component of \(G[C^+]\) without a neighbor of \(z\) would be a component of \(G-y\) with at most \(K\le K_m\) vertices; so \(G[C^+]\) has at most \(\min\{d(y),d(z)\}\) components. The rest of the first sentence follows from the definitions. Let \(\Delta\le7\). \(G\) is connected with \(|V(G)|>N_1=7K+2\ge\Delta K+2\), so \(R\ne\emptyset\) and not both \(o_y,o_z\) vanish. If \(o_z=0<o_y\), then \(C^+\cup\{z\}\) is a union of components of \(G-y\) with at most \((d(y)-1)K+1\le K_m\) vertices, and the multiplier reduction would apply; similarly if \(o_y=0<o_z\). If \(x=y\), all neighbors of \(x\) but \(z\) lie in \(C\), so \(o_y=0\).  ∎

In the branch \(G-y\) the vertex \(z\) cuts off every component of \(G[C^+]\), which the multiplier reduction deletes; in \(G-N[y]\) the components of \(G[C^+\setminus N[y]]\) are deleted by the multiplier reduction at \(z\) or, if \(yz\in E(G)\), solved directly. So the instances arise from \(I_1=G\ominus(\{y\}\cup C^+)\) and \(I_2=G\ominus(N[y]\cup C^+)\) by further reductions, which by Lemma C.13 do not increase \(\mu\); the same holds for \(z\), and for \(x\) with \(G\ominus\{x\}\) and \(G\ominus N[x]\).

Lemma C.18 (credit from a large part).  Let \(w_2>0\) and \(\Delta w_3\ge\dots\ge\Delta w_D>0\) with \(D\ge\Delta(G)\). Let \(X_0\subseteq V(G)\), \(S\subseteq V(G\ominus X_0)\), and let \(P\) be a connected set of vertices of \(G-X_0\), disjoint from \(S\), of vertices of degree at least \(2\), with \(N(P)\subseteq P\cup X_0\cup S\). Let \(W_P=P\cap W(X_0)\). Then the terms of the vertices of \(P\) in Lemma C.13 add up to at least \(e(P,X_0)\Delta w_D+|W_P|w_2-2[W_P=P]\Delta w_D\), and so to at least \(e(P,X_0)\Delta w_D\) if \(|P|>K\) and \(Kw_2\ge2\Delta w_D\).

Proof. Let \(P'=P\setminus W_P\). When \(t\in W_P\) is removed it has at most one remaining neighbor, its out-neighbor, in \(W_P\), \(P'\) or \(S\); let \(N_{\mathrm{out}},N_S,N_{\mathrm{iso}}\) count the \(t\) whose out-neighbor lies in \(P'\), lies in \(S\), or does not exist. Counting the edges at \(W_P\) at their later endpoints, \(e(X_0,W_P)=\sum_{t\in W_P}(d(t)-2)+N_{\mathrm{out}}+N_S+2N_{\mathrm{iso}}\). The vertices of \(P'\) contribute at least \((N_{\mathrm{out}}+e(X_0,P'))\Delta w_D\), and \(t\in W_P\) contributes \(w_{d(t)}\ge w_2+(d(t)-2)\Delta w_D\); so \(P\) contributes at least \(|W_P|w_2+(e(P,X_0)-N_S-2N_{\mathrm{iso}})\Delta w_D\). A component \(A\) of \(G[W_P]\) has \(e(A)=|A|-N_{\mathrm{out}}(A)-N_S(A)-N_{\mathrm{iso}}(A)\ge|A|-1\); if \(W_P\ne P\), its edge to \(P'\) is an out-edge, so \(N_S(A)=N_{\mathrm{iso}}(A)=0\). If \(W_P=P\), then \(G[W_P]\) is connected and \(N_S+2N_{\mathrm{iso}}\le2\).  ∎

Lemma C.19 (one section suffices).  Let \(I_1,I_2\) be the instances of a branching of \(G\). If \(\Delta(G)=4\), \(G\) has minimizing section \(k\), and \(a_j=\mu^{(k)}_{\mathrm{lin}}(G)-\mu^{(k)}_{\mathrm{lin}}(I_j)-[k=1]\psi\) satisfy \(2^{-a_1}+2^{-a_2}\le1\), then \(2^{\mu(I_1)}+2^{\mu(I_2)}\le2^{\mu(G)}\). The same holds for \(\Delta(G)\ge5\) with \(a_j=\sum_iw_in_i(G)-\sum_iw_in_i(I_j)\) for the weights (C.12) or (C.13).

Proof. It suffices that \(\mu(G)-\mu(I_j)\ge a_j\). For \(\Delta(G)=4\), \(\mu_4(G)=\mu^{(k)}(G)\ge\mu^{(k)}_{\mathrm{lin}}(G)\), and \(\mu(I_j)\le \mu^{(k)}_{\mathrm{lin}}(I_j)+[k=1]\psi\): for \(\Delta(I_j)=4\) as \(\mu_4\le\mu^{(k)}\), and for \(\Delta(I_j)\le3\) as \(\mu(I_j)\le\mu^{(1)}_{\mathrm{lin}}(I_j)\le \mu^{(k)}_{\mathrm{lin}}(I_j)\) by (C.10). For \(\Delta(G)\ge5\), an instance of maximum degree at most \(4\) has measure at most \(\mu^{(5)}_{\mathrm{lin}}\), or at most \(\frac5{32}n_3+\frac14n_4\), and both are at most \(\sum_iw_in_i\).  ∎

The three candidates.

For \(X_0\subseteq V(G)\), the \(H\)-clean-up deletes \(X_0\cap V(H)\) from \(H\) and then removes vertices of degree at most \(1\), where \(y\) and \(z\) count \(o_y\) and \(o_z\) extra edges to vertices never removed. Let \(W'\) be the removed vertices, \(d'(v)\) the final degree of a surviving \(v\in V(H)\), and \(\ell_R\) the number of edges between \(R\) and \(\{y,z\}\cap(X_0\cup W')\). Let \[\beta(X_0)=\sum_{v\in(X_0\cap V(H))\cup W'}w_{d(v)} +\sum_{v\in V(H)\setminus(X_0\cup W')}\bigl(w_{d(v)}-w_{d'(v)}\bigr)+\ell_R\,\kappa',\] with \(\kappa'=\Delta w_D\) if \(X_0\subseteq V(H)\) and \(\kappa'=\min\{w_2,\Delta w_D\}\) if \(X_0=N[v]\cup C^+\) with \(v\in\{y,z\}\). The candidate vectors are \(\bigl(\beta(\{v\}\cup C^+),\max\{\beta(\{v\}\cup C^+)+o_vw_2,\beta(N[v]\cup C^+)\}\bigr)\) for \(v\in\{y,z\}\) and \((\beta(\{x\}),\beta(N[x]))\), each component reduced by \(\psi\) in section \(1\).

Lemma C.20 (the candidates).  In a lazy configuration, let the weights be nondecreasing with \(w_2>0\) and \(\Delta w_3\ge\dots\ge\Delta w_D>0\), \(D\ge\Delta\), and \((K+1-\Delta)w_2\ge2\Delta w_D\). Then each candidate vector is a lower bound on the decreases of \(\mu_{\mathrm{lin}}=\sum_iw_in_i\) in the two branches of its branching. Consequently, by Lemma C.19, if one candidate vector \((a,b)\), computed with the weights of the minimizing section for \(\Delta=4\) and with (C.12) or (C.13) for \(\Delta\ge5\), has \(2^{-a}+2^{-b}\le1\), the hybrid rule branches validly.

The hypothesis holds for \(K\ge65\) and all our weights: \(2\Delta w_D/w_2\) is largest for \(\Delta=D=4\) in section \(1\), where it is \(61.03<62\le K+1-\Delta\).

Proof. By Lemma C.13 the decrease from \(G\) to \(G\ominus X_0\) is a sum of nonnegative terms. The \(H\)-side: by induction on the removal order, \(W'\subseteq W(X_0)\), since a vertex of \(W'\) has at most one neighbor left in \(G-X_0\) when it is removed in \(H\) (vertices of \(C^+\) have no neighbor in \(R\)). So every \(v\in(X_0\cap V(H))\cup W'\) contributes \(w_{d(v)}\), and every other \(v\in V(H)\) either lies in \(W(X_0)\) and contributes \(w_{d(v)}\ge w_{d(v)}-w_{d'(v)}\), or survives with \(d_{G\ominus X_0}(v)\le d'(v)\), as it loses its edges to \(X_0\cup W'\); so \(H\) contributes at least the first two sums of \(\beta(X_0)\). The \(R\)-side, \(X_0\subseteq V(H)\): with \(X'_0=X_0\cup(W(X_0)\cap V(H))\), \(G\ominus X'_0=G\ominus X_0\), and each component \(P\) of \(G[R]\) satisfies Lemma C.18 with \(X'_0\) and \(S=\{y,z\}\setminus X'_0\); so \(R\) contributes at least \(\ell_R\,\Delta w_D\). The \(R\)-side, \(X_0=N[y]\cup C^+\): each \(r\in N(y)\cap R\) is deleted and contributes \(w_{d(r)}\); if \(z\in X_0\cup W'\), each \(s\in(N(z)\cap R)\setminus N(y)\) contributes \(w_2\) if removed and \(\Delta w_{d(s)}\) otherwise, and \(s\in N(y)\cap N(z)\cap R\) has \(d(s)\ge3\) (else \(\{s\}\subseteq C^+\)) and contributes \(w_{d(s)}\ge2\min\{w_2,\Delta w_D\}\); so \(R\) contributes at least \(\ell_R\kappa'\). The term \(o_yw_2\): with \(X=\{y\}\cup C^+\) and \(X'=N[y]\cup C^+\), \(G\ominus X'= (G\ominus X)\ominus(X'\cap V(G\ominus X))\), so by Lemma C.13 the second branch gains at least \(w_2\) over the first for each \(s\in N(y)\cap R\) that survives in \(G\ominus X\). Each other \(s\in N(y)\cap R\) lies in \(W_P\) for a component \(P\) of \(G[R]\), and by Lemma C.18, applied in the first branch with \(X^\circ=X\cup(W(X)\cap V(H))\) in place of \(X_0\), \(P\) contributes at least \(e(P,X^\circ)\Delta w_D+|W_P\cap N(y)|w_2\): trivially if \(W_P\ne P\), and if \(W_P=P\) because \(|P\setminus N(y)|\ge K+1-\Delta\) and \((K+1-\Delta)w_2\ge2\Delta w_D\). The case of \(z\) is symmetric.  ∎

Lemma C.21 (the branching on \(y\) in closed form).  In a lazy configuration, with the weights as in Lemma C.20, let \(\zeta=w_{d(z)}-w_{o_z}\) if \(o_z\ge2\) and \(\zeta=w_{d(z)}+\Delta w_D\) if \(o_z=1\), and \[L=w_{d(y)}+\sum_{c\in C^+}w_{d(c)}+\zeta+o_y\,\Delta w_D.\] Then the candidate vector of \(y\) is at least \((L,L+o_yw_2)\). \(L\) does not decrease when vertices are added to \(C^+\) or degrees grow, with \(o_y,o_z\) fixed. If \(L-[k=1]\psi\ge1\), with \(k\) the minimizing section when \(\Delta=4\), the branching on \(y\) satisfies the condition of Lemma C.1.

Proof. For \(X_0=\{y\}\cup C^+\), \(W'\subseteq\{z\}\); if \(o_z\ge2\), \(z\) survives with \(d'(z)=o_z\) and \(\ell_R=o_y\), and if \(o_z=1\), \(z\) is removed and \(\ell_R=o_y+1\). So \(\beta(X_0)=L\). The monotonicity holds as the weights are nondecreasing and \(w_2>0\), and the last claim by Lemma C.20, as \(2\cdot2^{-1}=1\).  ∎

Corollary C.22 (maximum degree at least \(7\)).  The branching on \(y\) of a lazy configuration satisfies the condition of Lemma C.1 if \(\Delta=7\) with the weights (C.13), and for the measures \(w_6|V|\) (\(\Delta\ge7\)) and \(w_7|V|\) (\(\Delta\ge8\)).

Proof. For \(\Delta=7\) and (C.13), Lemma C.17 gives \(x\in C^+\) and \(|N(x)\cap C^+|\ge5\), so \(L>w_3+w_7+5w_2=1.041919\). For the measures \(w_6|V|\) and \(w_7|V|\), both branches delete \(\{y\}\cup C^+\), which contains \(y\), \(x\) and \(N(x)\setminus\{y,z\}\), at least \(\Delta\) vertices, and for \(\Delta=7\) the branch \(G-N[y]\) also deletes the \(o_y\ge1\) neighbors of \(y\) in \(R\). With \(\lambda<2^{w_6}\) the root of \(\lambda^8=\lambda^7+1\), \(2^{-7w_6}+2^{-8w_6}<\lambda^{-1}+\lambda^{-8}=1\), and \(2\cdot2^{-8w_6}<0.38\), \(2\cdot2^{-8w_7}<0.39\).  ∎

For \(\Delta\ge5\) a type is admissible if it contains a degree smaller than \(\Delta\), which holds in non-regular components.

Lemma C.23 (thresholds for the branching on \(y\)).  The branching on \(y\) satisfies the condition of Lemma C.1 in every lazy configuration with an admissible type of \(x\) in which

(1)  \(\Delta=4\) and the minimizing section is \(4\) or \(5\);

(2)  \(\Delta=4\), the minimizing section is \(2\) or \(3\), and \(\bar e\ge2\) or some vertex of \(C^+\setminus N[x]\) has degree at least \(3\);

(3)  \(\Delta=4\), the minimizing section is \(1\), and some vertex of \(C^+\setminus\{x\}\) has degree at least \(3\);

(4)  \(\bar e\ge1\), and \(\Delta\in\{5,6\}\) with (C.12) or \(\Delta=6\) with (C.13);

(5)  \(\bar e\ge2\), \(\Delta=5\) and (C.13).

Proof. By Lemma C.21 with \(D=\Delta\) it suffices that \(L-[k=1]\psi\ge1\). By Lemma C.17, \(d(x)=\Delta\), the degrees of \(N(x)\setminus\{y,z\}\) are those of the type, \(3\le d(y),d(z)\le\Delta\), \(1\le o_y\le d(y)-1\), \(1\le o_z\le d(z)-1\), and the \(\bar e\) vertices of \(C^+\setminus N[x]\) contribute at least \(\bar ew_2\), or \(w_3\) for one of degree at least \(3\). As \(L\) is monotone, the remaining parameters (type, whether \(y,z\in N(x)\), \(d(y),d(z),o_y,o_z\)) take finitely many values, and g2_thresholds.py (parts A and B) computes the minima of \(L\) exactly. They are \(1.0800248\) and \(1.2168722\) in (1); at least \(1.0236558\) in (2); \(L-\psi\ge1.0070736\) in (3); at least \(1.0050485\) in (4); and \(1.1052066\) in (5).  ∎

Theorem C.24 (the hybrid rule on bounded configurations).  In every lazy configuration of the following classes, one of the three candidate vectors \((a,b)\) satisfies \(2^{-a}+2^{-b}\le1\):

(1)  \(\Delta=4\), any minimizing section \(k\), an admissible type for section \(k\), and \(C^+=(N[x]\setminus\{y,z\})\cup E\) with \(|E|\le2\);

(2)  \(\Delta\in\{5,6\}\), an admissible type, and \(C^+=N[x]\setminus\{y,z\}\);

(3)  \(\Delta=5\), an admissible type, and \(C^+=(N[x]\setminus\{y,z\})\cup E\) with \(|E|\le1\);

in classes (2) and (3) with both weight vectors (C.12) and (C.13), and in each class optionally with one further vertex \(p\in C^+\) with \(N(p)=\{y,z\}\).

Code: g2_enumeration.py

Proof. The proof is computer-assisted (g2_enumeration.py, parts A and B). For each class the program generates every graph \(H\) on \(C^+\cup\{y,z\}\) with the prescribed degrees (all at most \(\Delta\), with \(d(y),d(z)\in[3,\Delta]\) enumerated independently of the type), and every pair \(o_y,o_z\ge1\). It skips \(H\) if some \(c\in C^+\) leaves a component of \(H-c\) without \(y\) and \(z\) (a part of \(G-c\) with at most \(K\le K_m\) vertices, so the multiplier reduction would apply), or if a component of \(G[C^+]\) misses \(y\) or \(z\) (Lemma C.17). For the others it computes the three candidate vectors in exact rational arithmetic and tests \(2^{-a}+2^{-b}\le1\) in floating point with margin \(10^{-9}\), and with \(40\) decimal digits in the doubtful band. About \(8.7\cdot10^6\) configurations are tested in class (1), \(4.1\cdot10^7\) in class (2) and \(2.1\cdot10^7\) in class (3) (the last two for each weight vector); none fails.  ∎

Lemma C.25 (the \(2\)-path family).  Let a lazy configuration with \(\Delta=4\) have all vertices of \(C^+\setminus\{x\}\) of degree \(2\). Replace every maximal path of vertices of degree \(2\) in \(C\) that starts at a neighbor \(u\) of \(x\) by \(u\) alone, joined to the end (\(y\) or \(z\)) of the path, and every other component of \(G[C^+]\), which is a path from a neighbor of \(y\) to a neighbor of \(z\), by one vertex \(p\) with \(N(p)=\{y,z\}\). The result \(H'\), with the same \(o_y,o_z\), satisfies all conditions that the proof of Theorem C.24 tests for class (1), with the same type, \(d(y),d(z),o_y,o_z\), and each candidate vector of \(H\) is componentwise at least that of \(H'\).

Proof. From \(u\in N(x)\setminus\{y,z\}\) the vertices of degree \(2\) lead to \(x\), \(y\) or \(z\); to \(x\) would give a component of \(G-x\) of at most \(K_m\) vertices. Two such paths are disjoint, and they cover \(C\). A component of \(G[C^+]\) other than \(C\) is not a cycle and has neighbors of \(y\) and \(z\) (Lemma C.17), so it is a path from \(y\) to \(z\); there are at most \(d(y)-o_y-1\le2\) of them. So \(H'\) has the same degrees at \(x,y,z\), at most two vertices outside \(N[x]\), no vertex skipped by the proof of Theorem C.24, and its part \(\{x\}\cup(N(x)\setminus\{y,z\})\) keeps a neighbor of \(y\) and one of \(z\), as the paths keep their ends. A path of degree-\(2\) vertices is removed by a clean-up as soon as an attachment vertex in \(\{x,y,z\}\) or a deleted vertex of the path goes, and keeps all degrees \(2\) otherwise; so the \(H\)- and \(H'\)-clean-ups remove the same vertices among \(x,y,z\) and the same paths, with the same \(\ell_R\), and \(\beta\) for \(H\) exceeds \(\beta\) for \(H'\) by the weights \(w_2\ge0\) of the extra removed vertices.  ∎

Proof of (G2). By Lemma C.20 it suffices that one candidate vector satisfies \(2^{-a}+2^{-b}\le1\); for \(\Delta\le7\), \(x\notin\{y,z\}\) and \(C^+\supseteq N[x]\setminus\{y,z\}\) (Lemma C.17). For \(\Delta=4\) let \(k\) be the minimizing section; the type of \(x\) is admissible for \(k\) (paragraph “Cross-section cases”). Sections \(4,5\): Lemma C.23(1). Sections \(2,3\): Lemma C.23(2), or class (1) of Theorem C.24. Section \(1\): Lemma C.23(3), or Lemma C.25 and Theorem C.24. For \(\Delta\in\{5,6\}\) the component is not regular, so \(x\) has an admissible type: Lemma C.23(4),(5) or classes (2), (3). For \(\Delta\ge7\): Corollary C.22.  ∎

The hybrid rule cannot be replaced by the branching on \(y\) alone:

Proposition C.26 (the branching on \(y\) alone fails).  For \(K=65\) there is a connected graph \(G\) with \(488\) vertices, \(\Delta(G)=4\), \(\delta(G)=2\), no cut vertex and minimizing section \(2\), all of whose vertices of degree \(4\) have type \((2,3,3,4)\), with a vertex \(x\) and a lazy \(2\)-separator \(\{y,z\}\subseteq N(x)\), \(d(y)=3\), for which both instances of the branching on \(y\) are \(G-\{x,u_1,u_2,y,r\}\) and \(2^{\mu_4(I_1)}+2^{\mu_4(I_2)}=1.0210061\cdot2^{\mu_4(G)}\).

Proof. Take \(m=80\) and the vertices \(a_i,a'_i,b_{i,1},b_{i,2},b_{i,3}\) (\(i\in\mathbb Z_m\)), \(c_i\) (\(i\in\mathbb Z_m\setminus\{0\}\)) and \(x,u_1,u_2,y,z,r,s_1,s_2,s_3\), with the edges \(a_ia'_i\), \(a_ib_{i,1}\), \(a_ib_{i,2}\), \(a'_ib_{i,2}\), \(a'_ib_{i,3}\), \(b_{i,1}b_{i,3}\), \(b_{i,2}b_{i,3}\) for all \(i\); \(a'_ic_i\), \(c_ia_{i+1}\) for \(i\ne0\); \(b_{i,1}b_{i+1,1}\) for even \(i\ne0\); and \(a'_0r\), \(ry\), \(yx\), \(yu_2\), \(xu_1\), \(xu_2\), \(u_1u_2\), \(xz\), \(zs_1\), \(s_1a_1\), \(zs_2\), \(zs_3\), \(s_2s_3\), \(s_2b_{0,1}\), \(s_3b_{1,1}\). In \(G-y\), \(z\) cuts off the part \(\{x,u_1,u_2\}\), which the multiplier reduction deletes, and \(r\) becomes pendant; in \(G-N[y]=G-\{y,x,u_2,r\}\), \(u_1\) loses both neighbors. So in both branches the vertices \(y,x,u_1,u_2,r\) disappear and \(z,a'_0\) drop from degree \(4\) to \(3\), so the decrease is \(2w^{(2)}_2+2w^{(2)}_3+w^{(2)}_4+2\Delta w^{(2)}_4=0.9700085\). The remaining properties are checked by part C of g2_enumeration.py.  ∎

References

Björklund, Andreas, Thore Husfeldt, and Mikko Koivisto. 2009. “Set Partitioning via Inclusion-Exclusion.” SIAM Journal on Computing 39 (2): 546–63. https://doi.org/10.1137/070683933.

De Ita Luna, Guillermo, J. Raymundo Marcial-Romero, Pedro Bello López, and Meliza Contreras González. 2026. “An Exact Algorithm for Counting the Number of Independent Sets of a Graph.” Mathematics 14 (2): 275. https://doi.org/10.3390/math14020275.

Edwards, Keith J. 2016. “A Faster Polynomial-Space Algorithm for Max 2-CSP.” Journal of Computer and System Sciences 82 (3): 536–50. https://doi.org/10.1016/J.JCSS.2015.11.013.

Fomin, Fedor V., Serge Gaspers, Saket Saurabh, and Alexey A. Stepanov. 2009. “On Two Techniques of Combining Branching and Treewidth.” Algorithmica 54 (2): 181–207. https://doi.org/10.1007/s00453-007-9133-3.

Fomin, Fedor V., and Kjartan Høie. 2006. “Pathwidth of Cubic Graphs and Exact Algorithms.” Information Processing Letters 97 (5): 191–96. https://doi.org/10.1016/j.ipl.2005.10.012.

Gaspers, Serge, and Edward J. Lee. 2016. “Faster Graph Coloring in Polynomial Space.” https://arxiv.org/abs/1607.06201v2.

———. 2023. “Faster Graph Coloring in Polynomial Space.” Algorithmica 85 (2): 584–609. https://doi.org/10.1007/S00453-022-01034-7.

Gaspers, Serge, and Gregory B. Sorkin. 2012. “A Universally Fastest Algorithm for Max 2-Sat, Max 2-CSP, and Everything in Between.” Journal of Computer and System Sciences 78 (1): 305–35. https://doi.org/10.1016/J.JCSS.2011.05.010.

———. 2014. “Separate, Measure and Conquer: Faster Polynomial-Space Algorithms for Max 2-CSP and Counting Dominating Sets.” https://arxiv.org/abs/1404.0753v2.

———. 2017. “Separate, Measure and Conquer: Faster Polynomial-Space Algorithms for Max 2-CSP and Counting Dominating Sets.” ACM Transactions on Algorithms 13 (4): 44:1–36. https://doi.org/10.1145/3111499.

Scott, Alexander D., and Gregory B. Sorkin. 2007. “Linear-Programming Design and Analysis of Fast Algorithms for Max 2-CSP.” Discrete Optimization 4 (3-4): 260–87. https://doi.org/10.1016/J.DISOPT.2007.08.001.

———. 2009. “Polynomial Constraint Satisfaction Problems, Graph Bisection, and the Ising Partition Function.” ACM Transactions on Algorithms 5 (4): 45:1–27. https://doi.org/10.1145/1597036.1597049.

Wahlström, Magnus. 2008. “A Tighter Bound for Counting Max-Weight Solutions to 2SAT Instances.” In Parameterized and Exact Computation, Third International Workshop, IWPEC 2008, Victoria, Canada, May 14-16, 2008. Proceedings, edited by Martin Grohe and Rolf Niedermeier, 5018:202–13. Lecture Notes in Computer Science. Springer. https://doi.org/10.1007/978-3-540-79723-4_19.