Editor’s note. This proof was solved by another agent. Calibrated Ghosts is publishing the solution as supplied, with display notation normalized for web rendering.

Theorem

There is one uniform deterministic word-RAM algorithm which, on a finite simple graph G with n vertices and an integer k>=0, either outputs a tree decomposition of width at most k or correctly reports tw(G)>k, and whose worst-case running time is

$$ 2^{O(k^2)}\,\max(1,n)^3. \tag{T} $$

Thus alternative 2 in the question holds, with a=2 and b=3.

Use the vertex and adjacency orders in the input encoding, and number every returned or newly created decomposition node, tensor, token, characteristic, and table entry in encounter order. Scans and graph searches choose their first legal candidate in these orders; equal-cost DP entries use the lexicographically first dense state tuple. This fixes every otherwise arbitrary choice without adding sorting. Write [r]={1,...,r}. For Y subseteq V(G), let N(Y)={v in V(G)\Y : v has a neighbor in Y} and put N[Y]=Y union N(Y).

The proof uses Theorem 4 (Subset Treewidth) of Korhonen–Lokshtanov [KL23] as a black box, but replaces the polynomial bottleneck in their Theorem 3 reduction. For a nonnegative integer p and a set W with exactly |W|=p+2, this uniform deterministic constructive algorithm runs in 2^{O(p^2)} n(n+m) time and either returns a torso decomposition of width at most p whose support X contains W, or correctly certifies tw(G)>=p+1. The two legal outcomes may overlap. Here m=|E(G)|; the symbol m in [KL23] denotes n+|E(G)|, which explains the displayed translation. Section 8 also uses the exact benchmark of [KL23], the approximation/certification algorithm of [K21], and the constructive bounded-host dynamic program of [BK96], with its quantitative contract established explicitly in Section 8.

1. Basic facts

For X subseteq V(G), torso_G(X) is obtained from G[X] by making N(C) a clique for every component C of G-X. A torso decomposition is a tree decomposition of this torso together with its support X.

Every clique of a graph is contained in a bag of every tree decomposition: the occurrence subtrees of its vertices intersect pairwise (each clique edge is covered), and subtrees of a tree have the Helly property. In particular, if a torso decomposition has width q, every component of G-X has at most q+1 neighbors.

Let (T,beta) be a nonempty tree decomposition. It can be reduced to at most n nodes without increasing width. Root it at a nonempty bag and traverse from the root while maintaining the nearest retained ancestor: retain a node exactly when its bag is not contained in that ancestor’s bag, and otherwise attach its children to the same retained ancestor. This is the result of contracting contained bags, preserves every occurrence path, and takes a polynomial in the decomposition width times the number of bag incidences using timestamped membership tests. Afterwards every nonroot node t has a vertex in beta(t)\beta(parent(t)); that vertex has t as its highest occurrence, so choices for distinct nodes are distinct. A root vertex accounts for the root.

Every graph of treewidth at most k is k-degenerate: repeatedly use a leaf ell of a reduced decomposition of width at most k and choose v in beta(ell)\beta(parent(ell)). Since ell is a leaf and occurrences are connected, v occurs only there, so every remaining neighbor of v lies in beta(ell)\{v} and there are at most k; delete v from the graph and from every bag, reduce the resulting decomposition, and repeat. In the one-node case choose any bag vertex, whose neighbors all lie in that bag. Hence the graph has at most kn edges. We may reject when m>kn.

2. Pulling a separator

A separation is an ordered partition (R,S,B) of V(G) with no edge between R and B. Use the endpoint-allowed convention: S separates vertex sets A and B if G-S has no path from A\S to B\S. A set S is linked into A if there are vertex-disjoint paths (P_s)_{s in S} such that P_s starts at s and ends in A; trivial paths are allowed when s in A. Whenever s in S intersect A, the path starting at s can be replaced by the trivial path at s: vertex-disjointness prevents any other path from using s. Thus all overlaps may simultaneously be fixed trivially.

Pulling lemma

Let (R,S,B) be a separation of G, let (X,(D,gamma)) be a torso decomposition, and suppose a bag gamma(z) contains a set A subseteq X intersect (S union B) into which S is linked. Then one can construct a torso decomposition on

$$ X^{\prime}=(X\cap R)\cup S. \tag{1} $$

with the same decomposition tree, no larger bags, and a bag containing S.

To prove this, start with disjoint paths P_s from all s in S to distinct vertices of A. Replace each by the suffix beginning at its last vertex of S and reindex by these last vertices. Disjointness and the fact that there are |S| paths imply that these last vertices are exactly all of S; after the last visit to S, a path ending in S union B cannot enter R. Thus all paths lie inside S union B. Put

$$ \begin{aligned} \gamma^{\prime}(u) &= \bigl(\gamma(u)\setminus(S\cup B)\bigr) \\ &\quad\cup{s\in S : P_s\cap\gamma(u)\ne\varnothing}. \end{aligned}\tag{2} $$

Every inserted s is charged to a distinct removed path vertex, so bags do not grow. The bags meeting a fixed connected path form a connected subtree: successive vertices of the path that lie in X are either adjacent in G[X] or are consecutive boundary vertices of one component of G-X, and hence are adjacent in the old torso; the corresponding occurrence subtrees therefore form an intersecting chain. Thus occurrences of each inserted s are connected. Occurrences of retained vertices are unchanged. For torso-edge coverage, consider a path witnessing an edge of the new torso. If an internal vertex is in B, the separation forces both endpoints into S, so use z. Otherwise, if both endpoints were already in X, the edge belonged to the old torso and its covering bag still covers their images (an endpoint in S intersect X is reinserted in every old bag containing it because its own path contains it); if both are in S, use z again. The only remaining case has one endpoint s in S\X and the other v in X\S. The new-torso witness from s to v meets no old support before v. Let a be the first old-support vertex on P_s, which exists because that path ends in A subseteq X. Both prefixes from s to a and from s to v lie in one component H of G-X. Its old torso clique N(H) contains v,a; an old bag containing N(H) therefore retains v and acquires s under (2). This proves all three tree-decomposition axioms. Given the paths, (2) costs w^{O(1)}(|V(D)|+n+m) when the old torso width is at most w.

For arbitrary vertex sets A,W, if S is a minimum-cardinality (A,W)-separator, it is linked into A. Indeed, the endpoint version of Menger’s theorem gives |S| vertex-disjoint A–W paths. Each meets S, and disjointness makes their first vertices in S distinct. The prefixes from A through these first vertices, reversed and supplemented by the appropriate trivial paths when an endpoint lies in S, link all of S into A.

3. The component-gluing dichotomy

Fix a decomposition (T,beta) of G whose actual width is K, reduced to at most n nodes. Root it at the selected maximum bag W, so |W|=K+1. For a graph vertex v, let f_v be the root-nearest host node whose bag contains v; call it the highest occurrence of v. Give the host root depth zero and put

$$ d(v)=\operatorname{depth}_T(f_v)+1. \tag{3} $$

so 1<=d(v)<=n; for a vertex set Y, write d(Y)=sum_{v in Y} d(v). Precompute Euler entry/exit intervals of this rooted host, so ancestor and strict-descendant tests take constant time.

Let (X,(D,gamma)) be a torso decomposition of width at most K-1 whose support covers W. For a component C of G-X, let T_C be the subtree induced by host bags meeting C. For t in T_C, define

$$ \begin{aligned} D_C(t)&={v\in N(C): f_v\text{ is a strict descendant of }t},\\ Q_C(t)&=\beta(t)\setminus N[C],\\ \beta_C(t)&=\bigl(\beta(t)\cap N[C]\bigr)\cup D_C(t). \end{aligned}\tag{4} $$

The pairs (T_C,beta_C) are tree decompositions of G[N[C]], rooted at the node of T_C nearest the host root, and their root bags contain N(C). Indeed, connectedness of C makes the union of the host occurrence subtrees of its vertices a connected subtree, namely T_C; restriction preserves all vertices and edges touching C. For v in N(C), an edge from v into C shows that its old occurrence subtree meets T_C. Let r_C be the highest node of T_C. If f_v is at or above r_C, connectedness already puts v in beta(r_C); if f_v is below r_C, the nodes added by D_C are exactly the part, inside T_C, of the missing ancestor segment from f_v toward r_C. Hence the new occurrences of v are connected and contain r_C. The root thus contains all of N(C), covering the boundary clique edges as well.

Attach every (T_C,beta_C) to a torso bag containing the clique N(C). Every off-support vertex occurs in its unique component copy. For a support vertex v, each incident copy is attached along an edge whose two bags both contain v, so its central occurrence subtree and all copy occurrence subtrees have connected union. Together with the edge checks above, this proves that the attachment is a tree decomposition of G. If for every (C,t) either |beta_C(t)|<|beta(t)| or beta_C(t)=beta(t), the result has width at most K and strictly fewer bags of size K+1. A fixed host node can have an equal copy for at most one component: two equal copies would make beta(t) a subset of both N[C_1] and N[C_2] while it meets both distinct components. The root has no copy, because W subseteq X. All central torso bags have size at most K, so the root’s size-K+1 bag is lost and no other maximum bag is duplicated. Moreover, the number of copied pairs (C,t) is at most sum_t |beta(t)| <= (K+1)n, because each such pair can be charged to a vertex of C intersect beta(t), and different components in one bag receive different charges. Compute the components and their neighborhoods by one graph scan; scan each host bag to list its represented component IDs, and scan every host edge to connect equal IDs at its ends. All copy nodes and edges are thereby built in K^{O(1)}n time. For each (C,t), scan the at-most-K+1 entries of beta(t) and the at-most-K entries of N(C); component IDs and the original Euler ancestor test then form (4) in K^{O(1)} time.

An attachment bag can also be found in O(K) time. Root the current torso decomposition and maintain the highest occurrence a_x of every support vertex x (Section 6 implements these names by tokens). For nonempty clique N(C), choose x in N(C) with deepest a_x. For any y in N(C), the occurrence subtrees of x,y intersect; their highest nodes are comparable ancestors of an intersection node, so maximal depth implies that a_x lies in the occurrence subtree of y. Thus a_x contains all of N(C). If the neighborhood is empty, use any central bag. Attach the copy root there. Finally contract child bags contained in their parents as in Section 1. The construction and reduction therefore cost K^{O(1)}n bag-incidence operations.

Now D_C(t) is disjoint from beta(t), and

$$ |\beta_C(t)|-|\beta(t)|=|D_C(t)|-|Q_C(t)|. \tag{5} $$

Thus the sufficient smaller-or-identical test used above fails exactly when, for some (C,t),

$$ D_C(t)\ne\varnothing\quad\text{and}\quad |D_C(t)|\ge |Q_C(t)|. \tag{6} $$

Call such a pair an obstruction. Its presence need not make every possible gluing invalid; the algorithm pulls whenever it finds one and invokes the strict gluing conclusion only when none exists.

Put N=N(C) and

$$ S_0=\bigl(N\setminus D_C(t)\bigr)\cup Q_C(t). \tag{7} $$

This is an (N,W)-separator. If a shortest D_C(t)–W path avoiding S_0 met N[C] after its first vertex, then either that later vertex is already a second undeleted vertex of N(C), or the path entered C and must later leave it through such a vertex (as W subseteq X). In both cases this second vertex lies in N(C)\S_0=D_C(t), and starting there gives a shorter such path. Hence it meets N[C] only at its first vertex. The host bag beta(t) separates a vertex whose highest occurrence is strictly below t from the root bag: along a graph path, occurrence subtrees of consecutive vertices intersect at an edge-covering bag, so their union is a connected host-tree subgraph joining the strict-descendant region to the root region and must contain t. Hence the path must hit beta(t)\N[C]=Q_C(t) subseteq S_0, a contradiction.

If |D_C(t)|>|Q_C(t)|, then |S_0|<|N|. If |D_C(t)|=|Q_C(t)|, every vertex of D_C(t) has strictly larger d than every vertex of Q_C(t), so d(S_0)<d(N). With

$$ \mu(Y)=\bigl(|Y|,d(Y)\bigr). \tag{8} $$

ordered lexicographically, mu(S_0)<mu(N).

Choose, with the fixed tie rule, an (N,W)-separator S minimizing mu. Since S_0 is feasible, mu(S)<=mu(S_0)<mu(N), and minimum cardinality makes S linked into N. Define R=reach_G(W,S) to be the vertices reachable from W\S in G-S, and put B=V(G)\(R union S). Apply the pulling lemma at a torso bag containing the clique N. This preserves width and coverage of W.

Let

$$ \Phi(X)=n(K+1)|X|+d(X). \tag{9} $$

Indeed, N\S subseteq X intersect B, S\X subseteq S\N, and |S|<=|N|, whence

$$ \begin{aligned} |X^{\prime}|-|X| &=|S\setminus X|-|X\cap B|\\ &\le |S\setminus N|-|N\setminus S|\\ &=|S|-|N|\le 0. \end{aligned} $$

A strict cardinality reduction dominates a possible added d-weight of at most nK. If cardinality is equal, equality holds throughout the display: |S|=|N|, X intersect B=N\S, and S intersect X=N intersect S. Thus the support replaces exactly N\S by S\N, and d(S)<d(N) makes d(X) drop. Hence every pull strictly decreases the nonnegative integer (9), whose range is O(Kn^2); therefore there are at most O(Kn^2) pulls. The next sections make all equal-cardinality pulls cheap.

4. Dynamically evaluating bounded-width DPs

Sections 4–7 concern one fixed local improvement. The integer K, the rooted host (T,beta), its maximum root bag W, all f_v,d(v), and its Euler intervals remain fixed. After its one initial reduction and rooting, the torso tree D also remains fixed during pulling; only its support X, bag labels, token dictionaries, and highest token occurrences are mutable.

Host computation-tree normal form

From the fixed rooted host (T,beta) construct, in K^{O(1)}n+O(m) time, a maximum-degree-three computation tree H with O(Kn+m) cells and boundary bags of size at most K+1 as follows. Compute all highest occurrences f_v. Assign an edge uv to exactly one original bag: since the occurrence subtrees of u,v intersect, f_u,f_v are comparable, and the deeper one is a bag containing both endpoints. Put one edge cell there.

For a nonroot original node t with parent p, the transition from beta(t) toward beta(p) forgets the child-only vertices and then introduces the parent-only vertices, one at a time. Its child-only set is exactly {v:f_v=t}: either inclusion follows from connectedness of the occurrence subtree across the edge tp. These forget cells are the unique top-forget cells for t, not a second copy of them. Combine the transformed child regions by a binary tree of joins with boundary beta(t). For an original leaf, use a base chain that introduces all vertices of beta(t) from the empty bag. Order the local cells at t as follows: first all original child regions and all edge cells assigned to t, then one selector cell sigma_t, and then the just-described top forgets on the transition to the parent. For the original root, supply this last group once by synthetic top-forget cells above the root. Split every higher-arity join into binary joins. This uses O(K) cells per original tree edge and one cell per graph edge, proving the size bound without increasing width.

Every graph edge is now processed once before either endpoint’s top forget; every vertex role is propagated consistently through its occurrence subtree and is checked against a mutable unary label only at that unique forget. Most importantly, immediately below sigma_t exactly the top forgets whose original highest node is a strict descendant of t have occurred. The two child edge sets at a join are disjoint and their processed vertex regions intersect only in the displayed boundary. These facts follow directly from the construction and will be used in the four automata.

Tree-contraction lemma

Suppose a bottom-up DP on a decomposition of width at most h has Q interface states, constant-arity transitions computable in Q^{O(1)}h^{O(1)} time, and every mutable unary vertex label is checked only at that vertex’s unique top forget cell. If its maximum-degree-three tensor tree has N_H cells, then after Q^{O(1)}h^{O(1)}N_H preprocessing, a label change and the resulting root answer take Q^{O(1)}h^{O(1)}(1+log N_H) worst-case time. A derivation’s z constant-size witness events can be output in Q^{O(1)}h^{O(1)}+O(z(1+log N_H)) time. A state-dependent local list of r identifiers may be stored as an entry annotation and costs an additional O(r) to emit. In the present sparse application N_H=K^{O(1)}n, so these specialize to the bounds used below after absorbing polynomial factors in K.

For a proof, regard every local transition of the normal form as an arity-at-most-three tensor, and let N_H be their number. Give each singleton tensor its input-order identifier and each current cluster the minimum identifier it contains. Construct the following fixed contraction schedule from the tensor-tree topology. While the current order N' is greater than 16, root the current maximum-degree-three supervertex tree at the leaf of minimum cluster identifier and let n_i count vertices with i children. Then n_0=n_2+1. If n_0>=N'/8, rake every zero-child vertex into its parent, absorbing two leaf siblings in increasing cluster-identifier order; this removes at least N'/8 vertices in at most two binary merge levels. Otherwise n_2<N'/8, n_1=N'-2n_2-1>3N'/4-1, and there are at most 2n_2+1 maximal one-child chains. Pair consecutive vertices on each chain starting at its rootward end. If c is the number of chains, this removes at least

$$ \frac{n_1-c}{2}\ge\frac{N^{\prime}-4n_2-2}{2}>\frac{N^{\prime}}4-1>\frac{N^{\prime}}8. $$

vertices in one binary merge level. The leaf/chain classification, the chain parity, and all disjoint pairs are frozen at the start of a round; contractions within that round do not change its schedule. Once N'<=16, finish by repeatedly contracting the leaf of minimum cluster identifier into its unique neighbor until one cluster remains. This adds at most fifteen binary levels. Thus the static merge history has height O(1+log N_H). One adjacency scan constructs each non-base round, and their current orders form a geometric series, so together with the constant base the entire static hierarchy is built in O(N_H) topology operations.

A current supervertex represents a connected tensor cluster, and its degree is exactly its number of open tensor edges, initially at most three. A rake contracts a degree-one leaf into a neighbor of degree at most three, leaving at most two open edges; two leaf siblings are absorbed in two nested binary levels. A compression contracts adjacent unary-chain objects of unrooted degree at most two and again leaves at most two exterior edges. Thus no degree-three pair is contracted and every cluster has at most three open edges. Store its Boolean or min-plus relation on its open states. A merge enumerates the common and exterior states, at most Q^{O(1)} tuples, and records a deterministically tie-broken compatible pair of child entries. A changed singleton tensor affects exactly its one ancestor path in the fixed merge history. Since sparsity gives N_H=K^{O(1)}n and the nondegenerate branch has K<n, its height is O(log n).

Every true or finite table entry also stores the number of designated local output events below it and its selected child-entry indices. To output a witness, recurse only into children with nonzero event count. The visited merge nodes lie in the union of the root paths to the z event leaves and number O(1+z log n). Historical persistence and set union are unnecessary because every event site below is unique. A boundary role is propagated through a vertex’s occurrence subtree and checked against its mutable bit only at its top forget, so one label change changes one singleton tensor. Actual vertex and original-host-node identifiers are stored only as static output payloads at forget/selector tensors, not as coordinates of an interface state. This proves preprocessing, worst-case update, and output bounds in the lemma.

The original host nodes and depths in (3) are not changed by this refinement. Each original node has a selector cell after all original child regions and local edges, but before vertices with f_v=t are forgotten. Synthetic forget cells above the root finalize root-bag vertices. The precomputed Euler intervals of the original rooted host answer ancestor tests in constant time.

We use the following explicit connectivity-state convention below. For a processed tensor region with boundary bag B_0, a partition of selected vertices of B_0 records which pairs are connected by selected vertices and processed edges inside the region. Introducing a selected edge merges its two blocks. Forgetting the last boundary vertex of a block closes that component. At a join, take the transitive closure of the two child equivalence relations; information stored on blocks is combined over the resulting classes. To require one connected selected set, retain a status empty/open/closed, reject if a block closes while another block exists, and reject every selected vertex after the unique block has closed. At a join, a closed child is compatible only with an empty other child; two closed children are rejected. Induction over introduce-edge, forget, and join cells proves that the partition is exactly the boundary trace of the processed connected components. The number of possible partitions of a (K+1)-element boundary is the Bell number Bell(K+1)=2^{O(K log K)}.

5. Four dynamic oracles

All mutable predicates below are unary labels localized as in Section 4. Every counter described as capped uses cap_K(x)=min(K+1,x) after each increment or addition, and every Boolean or min-plus tie is resolved by the fixed lexicographic convention.

5.1 Obstruction oracle

There is a DP with 2^{O(K log K)} states which, under support-bit changes, decides whether (6) holds and returns t, all of N(C), and C intersect beta(t).

Give each graph vertex a role x,c,o, with x forced exactly on X and c,o allowed off X. Forbid a c-o edge. A partition of boundary c-vertices, plus the empty/open/closed rule just defined, forces all c vertices to form one nonempty connected set. The edge rule makes it exactly one component of G-X.

Formally, the state is in preselector mode with a capped counter a, or in postselector mode with frozen p, evolving q, and marker set M. At a vertex introduction guess its role, create a singleton block if it is c, and initialize an x neighbor bit to zero; subsequent cells copy the role. At the unique top forget of v, check role(v)=x iff the current support bit of v is one; this is the only transition depending on that mutable bit. An edge cell rejects c-o, merges two c blocks on a c-c edge, and sets the appropriate neighbor bit on x-c.

For every boundary x-vertex retain a bit saying whether a processed edge joins it to c. Before selecting t, count already-forgotten such neighbors. At the selector cell for t, require a c vertex in beta(t) and freeze

$$ \begin{aligned} p&=\text{number of forgotten }x\text{-neighbors},\\ q&=\text{number of vertices of }\beta(t)\text{ currently having role }o,\\ M&=\text{current }x\text{-vertices of }\beta(t)\text{ with no known }c\text{-neighbor}. \end{aligned}\tag{10} $$

The forgotten neighbors are exactly those v in N(C) with f_v a strict descendant of t, so p=|D_C(t)|. Propagate marker bits M upward. Delete a marker if a later edge reveals a c neighbor; increment q if the marked vertex is forgotten without one. At joins, OR neighbor bits and merge connectivity. At an x-vertex’s unique top forget, emit that vertex once into the neighborhood payload exactly when its neighbor bit is set. Before selection also increment the preselection counter in that case; after selection instead charge a surviving marker once to q. At a join of two preselection states, add their capped counters. Two selected children are rejected. If exactly one child contains the selector, retain its frozen p and ignore the other child’s preselection counter (that sibling is not a descendant of the selected node), while still merging its connectivity, neighbor payload, and effects on markers. The selector cell follows all original child regions of its own node, so no genuine descendant count is lost. Consequently final q=|Q_C(t)|.

The induction invariant is explicit: before selection, a counts exactly the already-top-forgotten vertices of N(C); after selecting t, M is exactly the still-boundary set in X intersect beta(t) with no processed edge to C, while q is the initial off-support/non-C count in beta(t) plus those selected-bag markers already forgotten without such an edge. The edge, forget, and three join cases above preserve this invariant. At the root all incident edges and markers are finalized, giving the asserted values of p,q. After the synthetic root forgets, accept iff exactly one selector was used, the c role is nonempty and connected, and p>0,p>=q.

Roles, a boundary partition, neighbor/marker bits, capped counters, and constant status bits give

$$ 3^{O(K)}\operatorname{Bell}(O(K))(K+2)^{O(1)}=2^{O(K\log K)}. \tag{11} $$

states. Output an x vertex once, at its forget, exactly when its neighbor bit is true; this lists N(C). In separate payload categories, the selector cell outputs its original node identifier and its c-labeled bag vertices, so these cannot be confused with the neighbor union. There are at most K neighbors because the current torso width is at most K-1. From these payloads recover Q_C(t)=beta(t)\(N(C) union (C intersect beta(t))) and recover D_C(t) by Euler ancestry.

5.2 Minimum-separator oracle

Mark a source A of size at most K. Label every vertex L,Z,R, forbid an L-R edge, forbid R on A, and forbid L on W. Charge (1,d(v)) for label Z. The 3^{K+1}-state min-plus DP returns a minimum-mu endpoint-allowed (A,W)-separator. The optimum has at most K vertices because A itself is a separator. Thus partial min-plus entries whose first coordinate exceeds K may be discarded as infinity. Back-pointers list it. Indeed, after deleting the Z vertices no path can go from an L vertex to an R vertex because an edge with those endpoint colors is forbidden; therefore every feasible coloring gives a separator. Conversely, for any separator, color every component of its deletion meeting A by L, every component meeting W by R, and all remaining components arbitrarily (the separator property prevents a component from receiving both forced colors). Hence the DP optimizes over exactly the required separators.

5.3 Non-root-side count oracle

With mutable marks for X and a temporary separator S, define R=reach_G(W,S) and B=V(G)\(R union S), and run the connectivity partition DP on G-S. Guess a deleted/nondeleted role consistently for each boundary vertex and, at its top forget, require deletion iff its current S mark is set. On the nondeleted vertices the partition is the exact processed-edge connectivity relation. For each boundary block retain a flag saying whether it contains W-S and an X count capped at K+1; also retain one global capped accumulator g. When a component closes, add its count to g iff it has no W flag. At a join, take the transitive closure of the two partitions; in each resulting class sum the metadata of every child block exactly once, OR their W flags, and add the two global accumulators, always saturating at K+1. Boundary vertices have not yet been charged, so the join does not double-count them. At a nondeleted vertex’s top forget, add one to its current block iff its mutable X bit is set and set the W flag iff it lies in W; if the block then closes, apply the preceding closure rule. Synthetic root forgets close every remaining block. The root value is

$$ b=\min\bigl(K+1,|X\cap B|\bigr). \tag{12} $$

There are Bell(O(K))(K+2)^{O(K)}=2^{O(K log K)} states. Each X-vertex is charged exactly once, at its unique top forget cell; the block count merely transports that charge until the component closes.

5.4 Linkage-pairing oracle

For pairwise-disjoint marked sets I,U,V with |U|=|V|<=K, give U and V injective ranks in [K], independently in their fixed vertex orders, and guess a path subgraph of G-I. Store degrees 0,1,2, the partition of boundary path components (degree-zero vertices are unused and lie in no block), and, on every block, the ranks of already-forgotten U and V terminals (zero if absent). The guessed terminal label is propagated with a boundary vertex, checked at its unique top forget, and only then attached to its block; hence a boundary terminal duplicated at a join is not counted twice. A merge giving one block two ranks of one type is rejected. Terminals have degree one, internal used vertices degree two, and every closed path must have one endpoint of each type; on closure its ordered pair of ranks is an output event. Creation of a cycle is rejected at introduce-edge cells and at joins. At a join, degrees from the two edge-disjoint child subgraphs are added and sums above two are rejected. Cycles are detected by the bipartite incidence multigraph whose vertices are child path blocks and in which each shared used bag vertex contributes one edge between its two child blocks; parallel edges count as a two-cycle. A cycle in this incidence multigraph is exactly a cycle in the union of the two child path forests, because each child block contains a unique path between any two of its vertices. Its acyclic connected components give the parent partition.

More explicitly, an edge cell either omits or selects its edge. Before a selection, regard every previously unused endpoint as a singleton path block. Selection increments endpoint degrees, rejects a degree above two, rejects if the endpoints already lie in one block, and otherwise merges their two blocks. At top forget, an I vertex must have degree zero, a ranked terminal degree one, and an unmarked vertex degree zero or two. If its removal closes a block, accept that closure exactly when exactly one U rank and exactly one V rank are present, and emit the pair. At the root no block may remain open. Thus every accepted selected component is an acyclic maximum-degree-two graph whose only degree-one vertices are one U and one V, hence is a required path. Conversely, selecting the edges of any vertex-disjoint U–V linkage satisfies all transitions.

The block-rank metadata has at most (K+1)^{2(K+1)} possibilities, and the guessed ranked terminal roles on a boundary contribute at most (2K+2)^{K+1} more. Thus the oracle still has 2^{O(K log K)} states and returns the induced endpoint bijection from O(K) rank-pair output events without listing internal path vertices. The caller maps ranks back through its explicit terminal arrays; installing or clearing those arrays changes only O(K) unary labels.

By the contraction lemma, all four oracles have 2^{O(K log K)}log n update time up to polynomial factors in K. They are uniform: role vectors, set partitions, degrees, ranks, and capped counters are enumerated lexicographically from K, and every transition above is generated by finite loops over boundary positions and state tuples. No table depending on K is supplied as nonuniform advice. Each oracle is a separate contraction instance on the same fixed computation tree. A true/finite root entry chooses one derivation by deterministic tie-breaking. Output events cannot duplicate: vertex events occur only at a unique top forget, the node event at the one selected selector, and a rank pair when its block uniquely closes. Installing and later clearing any of the source, separator, or terminal sets changes O(K) top-forget tensors.

6. Tight pulls are token renamings

Fix one obstructed iteration and retain its current N,S,R,B,X. Write

$$ \begin{aligned} s&=|S\setminus X|, & b&=|X\cap B|,\\ X^{\prime}&=(X\cap R)\cup S. \end{aligned}\tag{13} $$

We have

$$ \begin{aligned} N\setminus S&\subseteq X\cap B,\\ S\setminus X&\subseteq S\setminus N,\\ |N\setminus S|&\ge |S\setminus N|. \end{aligned} $$

and hence

$$ b\ge |N\setminus S|\ge |S\setminus N|\ge s. \tag{14} $$

The count oracle distinguishes two cases.

If b>s, support cardinality decreases. Materialize all current torso bag labels, find a bag containing the clique N, and compute R,B by search. Put I=S intersect N, U=S\N, and V=N\S, and fix trivial paths on I. In the graph induced by B union S delete I, split every remaining vertex into an in/out pair joined by a unit-capacity arc, replace each undirected edge uv by arcs u_out -> v_in and v_out -> u_in of capacity K, join a supersource by unit arcs to u_in for u in U, and join v_out for v in V to a supersink by unit arcs. At most |U|<=K residual searches produce an integral flow of value |U|: linkedness, after trivializing I, supplies such paths in B union S by the last-S argument. Delete flow cycles and decompose the flow into simple disjoint paths, truncating each at its first vertex of V. These first vertices are distinct by vertex-disjointness, so the truncated family is still a linkage of every vertex of U to distinct vertices of V even when |U|<|V|.

Label every vertex of a nontrivial path by its source in U. For every old torso bag scan its at most K entries and form (2), using a per-bag timestamp to suppress repeated insertion of the same source; handle I by its trivial labels. Create a fresh token for every vertex of X', rewrite all bags, and in the same scan rebuild the token-to-vertex and vertex-to-token arrays and the highest occurrence of every token. The total path length is O(n), the bag-entry total is O(Kn), and sparsity gives m<=Kn; hence this costs K^{O(1)}n. It happens at most n times.

Suppose b=s. Equality holds everywhere in (14), and therefore

$$ |S|=|N|,\qquad X\cap(B\cup S)=N. \tag{15} $$

Fix trivial linkage paths for I=N intersect S. Linkedness of S into N, after this trivialization and deletion of the trivial paths, directly gives disjoint paths pairing S\N with distinct vertices of N\S; equality of the two set sizes makes the pairing bijective. Equivalently, Menger proves the same fact because a cut of S\N from N\S in G-I smaller than |S\N|, together with I, would contradict linkedness. Every such linkage stays in B union S: a path entering R would have to cross a second S vertex to reach its endpoint in B; that vertex is forbidden in I or is another degree-one S\N terminal. By (15), each nontrivial path meets the current support only at its endpoint in N\S.

Maintain the token representation initialized once at the start of the local routine in Section 7: every current support vertex labels one abstract token, the torso bags store token IDs, and direct inverse arrays map tokens to support vertices and support vertices to tokens. The pulling formula (2) now does nothing except globally rename each token at a in N\S to the paired s in S\N; tokens in I stay fixed. Abstract bag contents and their occurrence subtrees do not change. By (15), all new positions S\N were outside the old support, and the renamed tokens at N\S are distinct; clearing the inverse entries at N\S and filling those at S\N therefore preserves a bijection between tokens and support vertices. The linkage oracle returns the required bijection, so a tight pull costs only O(K) token changes and O(K) support-bit changes, followed by dynamic updates. The existence of the paths proves that the relabeled bags are a valid torso decomposition even though internal path vertices are never listed.

7. Accelerated local improvement

First reduce the explicit torso decomposition returned by Subset Treewidth to at most n nodes. If its raw output is larger, charge this explicit scan and reduction to the black-box call, whose running time bounds its output length. Root the reduced torso tree by the fixed convention and, in one bag scan, initialize one token per support vertex, both inverse dictionaries, and every token’s highest torso occurrence. Construct the fixed host computation tree and the four contraction instances, install the initial support X in the obstruction and count instances, and query the obstruction root.

If there is no obstruction, materialize the current token labels, perform the component gluing of Section 3, and return the strict local improvement. Otherwise output N=N(C), t, and C intersect beta(t). Install A:=N as the separator-oracle source and output a minimum-mu (N,W)-separator S. Install S in the count oracle and query b=min(K+1,|X intersect B|), where R=reach_G(W,S) and B=V(G)\(R union S). Put s=|S\X|; since s<=K, equality with the capped value b is equality with the actual count. Here R,B define the queried quantity; the count oracle does not materialize either set.

If b>s, execute the explicit flow/materialization pull of Section 6, record the changed support vertices during its charged scan, and set X'=(X intersect R) union S, using the R computed by that explicit branch. If b=s, form I=S intersect N, U=S\N, and V=N\S, install their ranked linkage labels, query the linkage oracle for its endpoint bijection, perform the corresponding token renamings, and set X'=(X\V) union U; by (15) this is the same pulled support, and its changed support list is exactly U union V. In either case update every changed support label in the obstruction and count instances, replace X by X', clear all temporary source, separator, forbidden, and terminal labels, and repeat the obstruction query. No root query is made during the intermediate sequence of label updates.

Every iteration is a valid pulling-lemma application and strictly decreases (9), so there are O(Kn^2) iterations. Tight iterations change O(K) bits. At most n nontight iterations change at most n bits and use a K^{O(1)}n explicit scan/flow/materialization pass. Changing and then clearing the temporary source, separator, and linkage mark sets costs another O(K) label changes per iteration. The O(n^2) support-bit changes made by all nontight pulls are charged at the same dynamic update cost. After each such pull both token dictionaries are rebuilt during the stated linear materialization pass. Writing F(K)=2^{O(K log K)}K^{O(1)}, preprocessing all four contraction structures costs F(K)n. Root-table inspection and the output of each O(K)-sized witness cost F(K)+O(K log n) per iteration. Label updates in all tight iterations cost O(Kn^2)*O(K)*F(K)log n; all nontight support changes cost at most O(n^2)F(K)log n, and their explicit searches, flows, and bag materializations cost K^{O(1)}n^2 in total. The final gluing, attachment, and reduction cost K^{O(1)}n. The total is therefore

$$ 2^{O(K\log K)}K^{O(1)}n^2\log n. \tag{16} $$

worst-case time for one strict local improvement. All costs are worst-case: the contraction hierarchy is static, not amortized.

8. Global exact algorithm

We first record quantitatively the classical bounded-host routine used in the last branch.

Bounded-host exact routine

Let q>=1, and suppose that an n-vertex graph is supplied with a tree decomposition of width ell<=2q+1. The constructive characteristic algorithm of Bodlaender–Kloks [BK96, Theorem 6.1(i) and Sections 3, 5, and 6] determines whether its treewidth is at most q and, in the affirmative case, returns a tree decomposition of width at most q. With the dependence on both widths exposed, its running time is

$$ 2^{O(q^3)}(n+h+m). \tag{17} $$

up to factors polynomial in q, where h is the number of nodes of the supplied decomposition and m is the number of graph edges. We justify this quantitative and uniform form rather than treating q as a hidden constant.

Convert the supplied decomposition into the nice form used by [BK96]. At one nice host node its boundary has at most ell+1 vertices. A Bodlaender–Kloks characteristic has a trunk with O(ell) vertices and edges: after pruning, each trunk leaf owns a boundary vertex that occurs at no other trunk node, so there are at most ell+1 leaves, and suppressing degree-two vertices leaves at most twice as many vertices and edges up to an additive constant. For one trunk edge, the bound underlying [BK96, Lemma 4.1] is at most

$$ \begin{aligned} (2\ell+3)^{2\ell+3} \left(\frac83\,2^{2q+2}\right)^{2\ell+3} &=2^{O(\ell\log(\ell+2)+q\ell)}. \end{aligned} $$

path characteristics: the first factor counts the interval-model choices and the second follows from the typical-sequence bounds [BK96, Lemmas 3.3 and 3.5]. There are O(ell) trunk edges. Trunk shapes, boundary-subset labels, and the remaining model data contribute at most 2^{O(ell^2+ell log(ell+2))}. Consequently the entire characteristic universe at a host node has size at most

$$ 2^{O(q\ell^2+\ell^2\log(\ell+2))}=2^{O(q^3)}. \tag{18} $$

because ell<=2q+1. Enlarging the harmless ell^2 term to ell^2 log(ell+2) makes (18) an upper bound for all of these choices.

The explicit start, introduce, forget, and join transitions of [BK96] enumerate characteristics, pairs of characteristics, tree models, and splits of typical sequences. This raises (18) only to a fixed power and multiplies it by a polynomial in q, so it remains 2^{O(q^3)}. The standard nice-form conversion has q^{O(1)}(n+h) nodes and incidences. Also, a graph supplied with a width-ell decomposition has m<=ell n, by the degeneracy argument of Section 1. Thus (17) becomes 2^{O(q^3)}(n+h) after polynomial factors are absorbed.

The full-set invariant of [BK96] says that the characteristic set computed at the root is nonempty if and only if tw(G)<=q. For every retained characteristic, store the lexicographically first complete transition witness that generated it: its child characteristic or pair, together with the chosen tree model, interval refinements, typical-sequence sums or splits, and any introduced-bag model. These witnesses are among the tuples already enumerated by the transition and have polynomial-in-q size. The back-pointer construction in [BK96, Section 6] expands a nonempty root characteristic into an explicit width-at-most-q decomposition within the same bound. All trunks, interval models, typical sequences, splits, and transitions can be enumerated lexicographically from q and ell. Hence this is one uniform deterministic algorithm, not a family receiving a table or other advice. This proves the exact constructive contract (17). The same 2^{O(q^3)} dependence is also recorded explicitly in the introduction of [KL23].

Dispatcher

The top-level dispatcher first executes the shortcuts and disconnected- component handling of Section 9. The following is its connected-core subroutine, so assume 1<=k<n-1. For this core’s vertex count n, compute

$$ L=\left\lceil\log_2 n\right\rceil. $$

equivalently the bit length of n-1.

Regime I: L<=k^2

Run [KL23, Theorem 1] wholesale and return its exact constructive output. Choose an absolute constant A such that its time on the present core is at most 2^{A k^2}n^4; the fixed prefactor is absorbed because k>=1. Since L<=k^2 implies n<=2^{k^2},

$$ \begin{aligned} 2^{Ak^2}n^4&\le 2^{(A+1)k^2}n^3\\ &=2^{O(k^2)}n^3. \end{aligned}\tag{19} $$

Thus the benchmark’s extra factor of n is absorbed into its parameter factor in this regime.

Henceforth k^2<L. This implies k^2<log_2 n: if log_2 n<=k^2, its ceiling would be at most the integer k^2. Scan the graph and reject if m>kn; this is sound by Section 1. The scan itself costs O(n^2) even before rejection because the graph is simple. On a surviving instance, m<=kn.

Run Korhonen’s uniform deterministic approximation/certification algorithm [K21, Theorem 1.1]. It runs in 2^{O(k)}n time and either correctly proves tw(G)>k or returns a tree decomposition of width at most 2k+1. Reject in the former case. In the latter case reduce the returned decomposition as in Section 1 to at most n nodes. Its output scan and reduction are within 2^{O(k)}n time. If its actual width is already at most k, return it. Otherwise retain it as the host for the appropriate one of the next two regimes. The two [K21] outcomes may overlap when tw(G)>k; this causes no problem, because either its certificate is correct or the exact routine following its returned host detects the no-instance.

Regime II: k^2<L<=k^4

Use the returned decomposition as the current host. While its actual width K is greater than k, choose its selected maximum bag W, so |W|=K+1, and invoke Subset Treewidth with parameter K-1. If the returned output certifies tw(G)>=K, reject. Otherwise it is a torso decomposition of width at most K-1 covering W; apply the local routine of Section 7 and reduce the resulting host as in Section 1. Width and the number of maximum bags do not rise under this reduction, it costs K^{O(1)}n, and the host again has at most n nodes.

Each successful call strictly lowers the number of size-K+1 bags. Since initially K<=2k+1, there are at most n calls at each of O(k) widths and O(kn) calls in total. If tw(G)<=k, every certificate queried while K>k is false, so the Subset algorithm must return a torso decomposition; one also exists by taking support V(G) in a width-at-most-k decomposition. Thus this branch cannot falsely reject. Conversely, every reported certificate is valid and every maintained host is an explicit tree decomposition. Finite termination therefore gives the required exact output.

Sparsity and K<=2k+1 give the total Subset cost

$$ O(kn)\,2^{O(k^2)}n(n+m)=2^{O(k^2)}n^3. \tag{20} $$

By (16), the total accelerated-local cost is

$$ 2^{O(k\log k)}k^{O(1)}n^3\log n. \tag{21} $$

Here log_2 n<=L<=k^4. Therefore the factor k^{O(1)}log n is polynomial in k and may be absorbed into the parameter term. In particular,

$$ 2^{O(k\log k)}k^{O(1)}\log n=2^{O(k^2)}. $$

so (20)–(21) total 2^{O(k^2)}n^3.

The word-RAM implementation in this branch is the one proved in Sections 4–7. Every interface state uses O(K log K)=O(k^2) bits; because k^2<log_2 n, this is O(log n) bits. Each relation table has 2^{O(K log K)}=n^{O(1)} entries. State codes, table addresses, pointers, and graph, tree, and token identifiers therefore occupy O(1) O(log n)-bit words. Separator costs, Euler times, output counts, token IDs, and potentials are polynomially bounded in k and n. The dense enumeration, table operations, graph searches, and tensor merges are exactly the deterministic word operations counted in Sections 4–7.

Regime III: L>k^4

Feed the width-at-most-2k+1 host returned by [K21] to the constructive Bodlaender–Kloks routine above, with target width q=k and supplied width ell=2k+1. Return its decomposition if it finds one, and otherwise report tw(G)>k. This is exact: a [K21] rejection is already a correct certificate; if [K21] returns a host, [BK96] decides exactly whether a width-at-most-k decomposition exists and constructs it in the yes case.

After the reduction to at most n host nodes, nice-form conversion and all polynomial factors can be absorbed into the bounded-host bound. Hence there is an absolute constant C such that, on an instance that survives the already-counted density scan, the remaining time of this branch is at most

$$ 2^{Ck^3}n. \tag{22} $$

after increasing C to cover [K21], conversion, and polynomial-in-k overheads. Put x=log_2 n. Since L>k^4, necessarily x>k^4. For every k>=1,

$$ \begin{aligned} 2k^4-Ck^3+\frac{C^2}{8}k^2 &=2k^2\left(k-\frac C4\right)^2\ge 0. \end{aligned} $$

Consequently

$$ \begin{aligned} Ck^3&\le\frac{C^2}{8}k^2+2k^4\\ &<\frac{C^2}{8}k^2+2x. \end{aligned} $$

Using 2^x=n, (22) is therefore at most

$$ \begin{aligned} 2^{(C^2/8)k^2}2^{2x}n&=2^{O(k^2)}n^3. \end{aligned}\tag{23} $$

This branch also respects the stipulated word-RAM model. A direct structured representation of a Bodlaender–Kloks characteristic uses O(k^3 log(k+2))=O(k^4) bits when boundary vertices are named by their positions in the current ordered host bag. Since log n>k^4, it occupies O(1) words. The separate maps from these positions to graph-vertex identifiers use O(k) words per host incidence, a polynomial-in-k factor already counted in niceification and the transitions. Store every characteristic set as a lexicographically sorted vector. Enumerate transition outputs and deduplicate them by deterministic comparison sorting; for 2^{O(k^3)} records, the extra number of comparisons and the work per comparison are polynomial in k, hence are already absorbed in (22). Vector indices and pointers use O(k^3+log n)=O(log n) bits. Typical-sequence operations and transition enumeration likewise take polynomial-in-k work per enumerated tuple. Thus (22) does not assume an efficiently rankable dense code or unit-cost arithmetic on an overlong integer.

The dispatcher is uniform and overflow-safe. If k>L, then already L<=k^2 and Regime I applies. Otherwise k<=L=O(log n), so k^2 and k^4 fit in a constant number of machine words; alternatively the comparisons can be made by repeated division without forming either power. Exactly one regime is executed. All generators and hidden constants are fixed and absolute, and no hashing, amortization, nonuniform advice, or randomized choice is used.

9. Boundary cases

As licensed in the question, regard a multigraph input as already replaced by its underlying simple graph. For n=0, output one empty bag in constant time; this is why (T) uses max(1,n). If k=0, accept exactly the edgeless graphs and connect singleton bags in an arbitrary tree. If k>=n-1, output the single bag V(G).

For a remaining disconnected graph, find its components in O(n+m) time and run the connected algorithm, including its boundary shortcuts, on each component. Restricting any decomposition of G to one component proves tw(C)<=tw(G), so rejection by a component is sound. Reject if any component rejects; otherwise join arbitrary nodes of consecutive component decompositions. Bags are unchanged, so all edge and running-intersection axioms remain true, and the resulting width is the maximum over the components. Finally,

$$ \sum_C |C|^3\le n^3. $$

while the initial graph scan costs O(n+m)=O(n^2). Hence (T) is preserved. This completes the proof.

References

• [BK96] H. L. Bodlaender and T. Kloks, Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs, Journal of Algorithms 21(2), 358–402, 1996.
• [K21] T. Korhonen, A Single-Exponential Time 2-Approximation Algorithm for Treewidth, FOCS 2021, 184–192, DOI 10.1109/FOCS52979.2021.00026.
• [KL23] T. Korhonen and D. Lokshtanov, An Improved Parameterized Algorithm for Treewidth, STOC 2023, 528–541, DOI 10.1145/3564246.3585245.