betaFeedback

WorksComputer Science

Counting Feedback Vertex Sets of All Sizes in Subexponential Time, Conditionally

Abstract

Assuming a Boolean tensor contraction hypothesis (Theorem D.1 of OpenAI's recent preprint refuting the Exponential Time Hypothesis), we study exact feedback vertex set counting in general graphs. For an nn-vertex, mm-edge simple graph, we compute the complete size distribution deterministically in poly(n+m) 2O(n(log⁡log⁡n)2/log⁡n)\mathrm{poly}(n+m)\,2^{O(n(\log\log n)^2/\sqrt{\log n})} time and polynomial working space. The algorithm combines a whole-edge forest identity, subset-index scalar networks, sparse parity filtering, and disjoint high-degree branching. A binomial inversion recovers the multiplicities introduced by exceptional-set guesses. The counting interface supports fixed vertices, minimum solutions, and unranking. Component markers yield induced-tree and induced-path counts within the same bound. Sparse Hamilton, forest, and Steiner edge-tree counting follow from the scalar encoding.

Introduction

Problem and motivation

A feedback vertex set removes all cycles of a graph. Counting these sets by size describes the full feasible-size distribution and supports minimum-solution recovery and unranking. The global constraint is acyclicity of the retained induced graph; arbitrary input density makes a direct incidence encoding expensive.

Main results

Let GG be a simple undirected graph with nn vertices and mm edges. A selector pin requires an original vertex to be retained or deleted; unranking returns the deletion set with a specified rank in a fixed vertex order. The tensor-contraction premise is stated precisely in Hypothesis 1.

Theorem 1 (General-graph exact FVS counting). Assuming the Hypothesis 1, every simple undirected nn-vertex graph admits deterministic computation of all feedback vertex set cardinality counts in

poly⁡(n+m)2O(n(log⁡log⁡(n+4))2log⁡(n+2))(1)\operatorname{poly}(n+m)2^{O\left(\frac{n(\log\log(n+4))^2}{\sqrt{\log(n+2)}}\right)} \tag*{(1)}

time and polynomial working space, with no density restriction. The same bound permits arbitrary original selector pins, a minimum feedback vertex set, and unranking a deletion set of a given size. Enumeration has this delay and polynomial working space, apart from writing the output.

The density-sensitive oracle is Theorem 6. Component markers give Theorem 8, including induced trees and paths. Sparse Hamilton, forest, and Steiner edge-tree consequences are collected in § 7.1.

Technical overview

The algorithm separates the algebra of acyclicity from the cost of representing a graph. A forest identity supplies exact cancellation, while a sequence of encodings makes that identity small enough for the contraction theorem [8 Theorem D.1]. The final reduction handles graph density outside the algebraic calculation. Figure 1 summarizes these roles; the details below explain why each arrow is needed.

The counting reduction

Figure 1. The counting reduction. Compression and filtering construct the leaf oracle; branching and inversion extend it to arbitrary density.

A forest identity supplies the counting object. The starting point is the Grassmann identity in § 2.1. Its top coefficient is a generating polynomial for forests, with one variable recording the number of selected edges. The signs cancel cyclic edge selections. Feedback vertex counting asks for induced forests: after choosing retained vertices, every edge between them must be present. Thus the desired object combines a vertex selection with an edge selection, and the two must agree. Keeping this distinction through the encoding is essential for recovering integer cardinality counts.

Compression pays for selected incidences. A direct incidence network has a wire for each graph incidence, so its size can grow with the number of edges. The algebraic expansion, however, uses only a bounded number of atoms at each selected term and at most linearly many selected terms. Subset indices encode these selected ports inside groups. Their entropy yields the density-sensitive scale n(1+log⁡(1+m/n))n(1 + \log(1 + m/n)). The Grassmann sign is then factored into ordinary scalar tensors. This step lets the external contraction algorithm operate on Boolean wires with scalar entries; the sign bookkeeping stays inside the local tensors. The wire count, maximum degree, and cost of evaluating an entry are tracked together.

Parity checks enforce whole-edge agreement. The compressed expansion contains auxiliary choices before cancellation. A parity test must refer to a whole graph edge, including both endpoint requirements, so that all monomial realizations of that edge receive the same test. Coefficientwise cancellation then preserves the forest identity within each tested object class. Sparse initial checks exclude low-weight discrepancies, and additional checks separate the remaining positive object counts. A weighted conditional-expectation oracle chooses these checks with polynomially many contraction queries. Its role is algorithmic as well as algebraic: it includes the cost of selecting the filter, the precision of its counts, and the local-entry cost of its weighted queries. Section 5 assembles these ingredients into the density-sensitive leaf counter.

High-degree branching makes the leaf counter useful on dense graphs. Every induced forest has few vertices whose retained degree exceeds a threshold tt. The outer algorithm guesses a set BB containing them. Outside BB, a retained vertex has at most tt retained neighbours. At a vertex with large current degree, a retaining branch specifies its exact retained-neighbour set and deletes all other neighbours; a deleting branch removes the vertex. Exact neighbour choices partition the solutions for this fixed BB. The process ends with a graph of bounded density, where the compressed counter applies with degree caps. Choosing tt of order log⁡n\sqrt{\log n} and the branching threshold of order (log⁡n)2(\log n)^2 keeps both the exceptional-set guesses and the leaf count within the final exponent.

Binomial inversion removes overlap between guesses. The branches for one BB are disjoint, but a forest can admit several exceptional-set guesses. A size-jj forest with hh genuinely high-degree retained vertices occurs in exactly (j−hk−h)\binom{j-h}{k-h} guesses of size kk. Summing the leaf counts by (j,k)(j,k) therefore gives a triangular binomial transform of the desired (j,h)(j,h) counts. Its diagonal entries are one. Successive integer subtraction recovers the distribution without division, and reversing the retained-size index gives the FVS distribution. This is the final recovery step in the proof of Theorem 1.

The same interface supports the stated applications. Pinned vertices are carried through the branches and the leaf network. Counting the two possibilities for the next vertex gives minimum-solution recovery and unranking. Component markers retain the statistics needed for induced trees and paths. Every outer guess, branch, and contraction call is processed sequentially; polynomial working space follows from storing one recursion path and polynomially many exact accumulators. The appendices supply the coefficient recovery, shift construction, and weighted-query details used by this proof skeleton.

Related work

Bodlaender, Cygan, Kratsch, and Nederlof [1] give deterministic integer counting for Hamilton cycles in O~(15twtwO(1)n2)\tilde{O}(15^{\mathrm{tw}}\mathrm{tw}^{O(1)}n^2) and Steiner trees in O~(10twtwO(1)n3)\tilde{O}(10^{\mathrm{tw}}\mathrm{tw}^{O(1)}n^3). Their structural parameter is treewidth. The FVS comparisons in Table 1 distinguish decision, optimization, and complete counting.

Source / taskBound and scope
Li–Nederlof [5]Randomized minimum FVS in O∗(1.6297n)O^*(1.6297^n) time.
Cut&Count [4]One-sided Monte Carlo FVS decision in 3twnO(1)3^{\mathrm{tw}}n^{O(1)} time on a tree decomposition.
This paperAll cardinality counts in poly⁡(n+m)2O(n(log⁡log⁡(n+4))2/log⁡(n+2))\operatorname{poly}(n+m)2^{O(n(\log\log(n+4))^2/\sqrt{\log(n+2)})} time; deterministic, polynomial space, under Hypothesis 1.

Table 1. Representative FVS bounds, with their output and assumptions. The parameters and tasks are stated explicitly.

Claude (Anthropic) [3], Theorem 1 gives a deterministic CNF counting bound with an absolute constant in 2O(min⁡{k2nlog⁡log⁡n/log⁡n,km/log⁡m})2^{O(\min\{k^2 n\log\log n/\sqrt{\log n},km/\sqrt{\log m}\})}. Our scalar encoding uses the ring-valued tensor interface of Theorem D.1.

The algebraic cancellation identities [2, 10], sparse parity framework [8], and induced-sparse-subgraph branching idea [7] provide the starting tools. Our contributions are the whole-edge scalar interface with complete wire and precision budgets, polynomial-query parity selection, and the disjoint branching with exact multiplicity recovery that together yield the all-density theorem.

Organization

Section 2 gives the contraction premise and forest identity. Section 3 states the complete algorithm and its dependencies. Sections 4 and 5 build its density-sensitive oracle; Section 6 proves the all-density theorem. The remaining sections give component and sparse companion counts. The appendices contain the detailed recovery and auxiliary constructions.

Preliminaries and contraction hypothesis

Graphs are simple and undirected unless arcs are specified. An FVS is a set DD for which G[V∖D]G[V \setminus D] is a forest. A singleton is a tree and a path; the empty forest has zero components. All logarithms are base two except where a natural logarithm is written. The notation poly denotes a fixed polynomial factor.

Hypothesis 1 (Theorem D.1 of OpenAI [8]). Let s≥2s \ge2 and let a bipartite Boolean tensor network have O(s)O(s) wires, polynomially many vertices, maximum degree at most ⌈s9/10⌉\lceil s^{9/10}\rceil, and description length L\mathcal{L}. Its entries lie in (Z/2P0Z)[V]/(Vℓ)(\mathbb{Z}/2^{P_0}\mathbb{Z})[V]/(V^\ell), with P0,ℓ=O(s)P_0,\ell= O(s). Suppose a local entry is computable in (s+L)O(1)2O(s9/10)(s+\mathcal{L})^{O(1)}2^{O(s^{9/10})} time and polynomial space. Then its contraction is computable deterministically in (s+L)O(1)2O(s/log⁡s)(s+\mathcal{L})^{O(1)}2^{O(s/\sqrt{\log s})} time and polynomial space.

Theorem 2 (Sparse parity checks, from [8 Lemma 6.1]). For positive integers mm, HH, put B=max⁡(1,⌈m/H⌉)B = \max(1, \lceil m/H \rceil), μ=⌊log⁡2m⌋+1\mu= \lfloor\log_2 m \rfloor+ 1, P=20000B2μ2P = 20000B^2\mu^2, and D0=320000B2μ3D_0 = 320000B^2\mu^3. There is a binary matrix with mm columns, at most 3H3H rows of support at most D0D_0, and no nonzero kernel word of weight less than m/Pm/P.

The local codes and shifts needed by this construction are made explicit below and in Appendix § 11. The imported sparse-check statement and Hypothesis 1 are used at their respective size parameters.

The forest identity

For forests, use the 2n2n Grassmann atoms ψˉ1,ψ1,…,ψˉn,ψn\bar{\psi}_1,\psi_1,\ldots,\bar{\psi}_n,\psi_n, set τv=ψˉvψv\tau_v = \bar{\psi}_v\psi_v, and let Top⁡\operatorname{Top} extract the coefficient of τ1⋯τn\tau_1\cdots\tau_n in canonical order. The imported forest identity is

Top⁡∏v(1+τv)∏uv∈E(1+UQuv)=∑F forestU∣F∣,(2)\operatorname{Top}\prod_v(1+\tau_v)\prod_{uv\in E}(1+UQ_{uv})=\sum_{F\ \mathrm{forest}}U^{|F|}, \tag*{(2)}

where Quv=(ψˉu−ψˉv)(ψu−ψv)−τuτvQ_{uv}=(\bar{\psi}_u-\bar{\psi}_v)(\psi_u-\psi_v)-\tau_u\tau_v. We replace each edge factor by the product of its five elementary monomial factors, and each vertex factor by its single mass factor. This is an integer identity: the even monomials commute, each has square zero, and all products of two distinct summands within QuvQ_{uv} cancel, since its quadratic part is decomposable and its quartic part overlaps it. Equivalently, the product is the finite exponential of UQuvUQ_{uv}, which equals 1+UQuv1+UQ_{uv}. Each elementary term has two or four physical atoms and grade one. There are O(n+m)O(n+m) ports. The degree in UU of each selected-term contribution is at most nn; cancellation gives the usual forest degree at most n−1n-1.

Algorithm and proof framework

The algorithm for Theorem 1 has an outer combinatorial reduction and an inner algebraic oracle. Its complete sequence is as follows.

  1. Choose the thresholds tt, DD of § 6 and enumerate exceptional retained sets BB of size at most bb from (24).

  2. For each BB, branch on high-current-degree vertices outside BB, specifying the exact retained neighbours in a retaining branch. The disjoint-leaf lemma in § 6 bounds the number and density of the leaves.

  3. Count each leaf by Theorem 6, with its original pins and degree caps. The scalar-network lemmas of § 4, exact separation in Lemma 5, and weighted oracle in Lemma 12 supply this call.

  4. Accumulate counts by retained size and exceptional-set size, then apply (29). Reverse the retained-size index to obtain every FVS cardinality count.

The correctness proof has two independent multiplicity arguments. The algebraic oracle cancels auxiliary expansions inside each graph object, and the outer binomial inversion corrects overlap among exceptional-set guesses. The proof in § 6 combines their costs and derives the final exponent. All calls are streamed to preserve polynomial space.

Selected-port compression with ordinary scalar tensors

Direct incidence networks for Hamilton cycles and forests use O(n+m)O(n+m) physical wires. We encode selected ports and factor the signs into ordinary scalar tensors. We put

s=n(1+log⁡2(1+m/n)),n≥2.(3)s = n\left(1+\log_{2}(1+m/n)\right), \qquad n \ge2. \tag*{(3)}

All graphs in this section are simple, so m=O(n2)m = O(n^{2}).

An ordinary network for signed covers of atoms

We use 2n2n ordered physical atoms, in adjacent pairs belonging to vertices. A term chooses an even-sized support of at most four atoms, a scalar coefficient, and a grade in {0,1}\{0,1\}. Grade-one atoms contribute the exterior inversion sign; grade-zero atoms contribute no such sign. Every selected term has even grade, so the sign is invariant under reordering selected terms. Every physical atom must be covered exactly once. Local conditions may require the two atoms of a vertex to have the same grade, or forbid grade one at a specified vertex.

For an optional term, assign its factor to the group of its smallest physical atom. We partition vertices into J=⌈n1/4⌉J = \lceil n^{1/4}\rceil consecutive groups, each of size at most ⌈n/J⌉\lceil n/J\rceil. The atom groups on the other side use the same partition. A bounded number of positive classical predicates can additionally be attached to a selected term; these receive their own column groups. For now ignore those classical ports.

We give each occurrence of an atom in a term its own port. A port belongs to a factor group gg, an atom group hh, and a grade cc. Let NghcN_{ghc} be the number of possible ports in that bucket. We enumerate their selected counts dghcd_{ghc}. Only 2n2n physical ports are selected, and each atom column has its prescribed total size. For a fixed count array, use

log⁡2(Nghcdghc)\log_{2}\binom{N_{ghc}}{d_{ghc}}

ordinary Boolean wires to index the selected subset, with unused binary codes assigned entry zero. Lexicographic subset decoding uses exact binomial coefficients of polynomial bit length, as in source Appendix § 13.§ 3.

The factor tensor checks that either every port of a term or none is selected. It multiplies the selected coefficients and the inversion sign of its own grade-one atoms, with terms in a fixed local order. The atom tensor checks exact coverage, the local grade conditions, and the inversion sign between grade-one atoms coming from different factor groups but lying in this atom group. Its ports specify both the atom identities and the supplying factor groups.

Lemma 3 (Complete scalar sign factorization). For a selected-port count array dghcd_{ghc}, let the local factor signs count inversions within each factor group and the local atom signs count inversions from distinct factor groups in the same atom group. Their product, multiplied by

(−1)χ(d),χ(d)=∑g<g′h>h′dgh1dg′h′1(mod2),(4)(-1)^{\chi(d)}, \qquad\chi(d)=\sum_{\substack{g<g'\\h>h'}} d_{gh1}d_{g'h'1} \pmod2, \tag*{(4)}

:::`

is exactly the exterior sign of the full selected grade-one sequence. Consequently summing the ordinary contractions over the count arrays equals the signed cover sum, with multiplicity one for every selection.

Proof. The proof partitions inversions according to their factor and atom groups. The terms are ordered by factor group and then by their local order. An inversion either has both atoms in one factor group, or has them in distinct factor groups. The former is counted by that factor tensor. In the latter case, equal atom groups are handled by the corresponding atom tensor, while distinct atom groups contribute precisely (4). These three cases partition all inversions. Grade-zero and classical ports contribute none. Every selected port set has one count array and one valid subset index per bucket; all-or-none and coverage checks give the converse correspondence.

Lemma 4 (Wire and degree budgets). Consider the subset-index construction of Section 4 restricted to factor rows and physical-atom columns, with classical predicate ports omitted. Put s=n(1+log⁡2(1+m/n))s = n(1+\log_{2}(1+m/n)). Suppose the input has I=O(n+m)I = O(n+m) ports, O(n)O(n) selected ports, and selected terms of bounded support. The signed cover sum is a sum of 2O(nlog⁡(n+2))2^{O(n\log(n+2))} ordinary networks, each with O(s)O(s) wires, maximum degree O(n3/4log⁡(n+2))O(n^{3/4}\log(n+2)), and polynomial-time local entries. The descriptions and their enumeration use polynomial space.

Proof. The proof bounds subset-index length by entropy and then controls the load at each tensor. There are O(J2)O(J^{2}) buckets. With K=O(n)K = O(n) selected ports, source Appendix D.3’s product bound gives

M≤O(J2)+log⁡2(I+KK)≤O(J2)+Klog⁡2e(I+K)K=O(s).(5)M \le O(J^{2}) + \log_{2}\binom{I+K}{K} \le O(J^{2}) + K\log_{2}\frac{e(I+K)}{K} = O(s). \tag*{(5)}

The arrays have at most (K+1)O(J2)(K+1)^{O(J^{2})} possibilities. Every selected optional term consumes its owner atom, so a factor group can contain only O(n/J)O(n/J) selected terms, even if many input terms have that owner. We discard arrays whose row sum exceeds the corresponding bounded-support cap. Each atom column has O(n/J)O(n/J) selected ports as well. Therefore the wire degree of either vertex is at most O(J+(n/J)log⁡(I+2))O(J+(n/J)\log(I+2)), which is the stated bound for simple graphs. This selected-load argument is essential: raw incidence degree can be much larger. Each local tensor decodes polynomially many bits, performs the explicit coverage and sign checks, and multiplies polynomial-bit coefficients. No local permanent or exponential subset sum is hidden in its entry procedure.

We will also use at most nn required factors, each a sum of a fixed number of even monomials. We put these factors in JJ additional rows, balancing their number. A row checks that exactly one alternative is selected per required factor. Its selected load is again O(n/J)O(n/J); the number of buckets and all bounds above change only by constants.

Whole-edge parity filtering for induced forests

Whole-edge indicators retain the edge factor selected in the forest identity. Sparse parity checks then separate the induced forests from all forest edge sets on selected vertices.

Edgeless graphs are handled directly. For compatible retained and deleted vertex pins, let d0d_0 be the number of vertices pinned deleted and ff the number of unpinned vertices. Every choice of the free vertices induces a forest, so the deletion-size generating polynomial is

Vd0(1+V)f.V^{d_0}(1+V)^f.

Its coefficients are computed in polynomial time; nonnegative upper bounds on retained degrees are automatically satisfied. This base case also covers empty graphs, single-vertex graphs, and edgeless residual instances.

For the remaining construction, let GG be a simple graph with n≥2n \ge2 vertices and m≥1m \ge1 edges. We set

L=1+log⁡2(1+m/n),H=n+⌊log⁡2(m+nn)⌋+1,p=H+1.(6)L = 1+\log_2(1+m/n), \qquad H = n+\left\lfloor\log_2\binom{m+n}{n}\right\rfloor+1, \qquad p=H+1. \tag*{(6)}

In particular H=O(nL)H=O(nL) and H≥n+1H\ge n+1. We consider the finite object set

Ω={(S,F):S⊆V(G), F⊆E(G[S]), F acyclic}.(7)\Omega=\{(S,F): S\subseteq V(G),\ F\subseteq E(G[S]),\ F\text{ acyclic}\}. \tag*{(7)}

We write zv=1v∈Sz_v=1_{v\in S} and fe=1e∈Ff_e=1_{e\in F}. Its violation coordinate is ve=zuzv+fev_e=z_u z_v+f_e (mod 2) for e=uve=uv. Thus v=0v=0 exactly when F=E(G[S])F=E(G[S]). Every induced forest has exactly one zero-violation object. Also

∣Ω∣≤2n∑j=0n(mj)≤2n(m+nn)<2H.(8)|\Omega|\le2^n\sum_{j=0}^{n}\binom{m}{j}\le2^n\binom{m+n}{n}<2^H. \tag*{(8)}

The second inequality follows by the Vandermonde convolution with (nj)≥1\binom{n}{j}\ge1. All counts refer to the objects in (7).

The parity filter and object-mass bound

For a binary matrix AA with mm columns, let

NA(V)=∑(S,F)∈Ω:Av(S,F)=0Vn−∣S∣,N(A)=NA(1).(9)N_A(V)=\sum_{\substack{(S,F)\in\Omega:\\ Av(S,F)=0}}V^{n-|S|}, \qquad N(A)=N_A(1). \tag*{(9)}

Every coefficient is nonnegative and N(A)<2HN(A)<2^H. We apply Theorem 2 with the object-mass parameter HH and

B=max⁡(1,⌈m/H⌉),μ=⌊log⁡2m⌋+1,B=\max(1,\lceil m/H\rceil), \qquad\mu=\lfloor\log_2 m\rfloor+1,
P=20000B2μ2,D0=320000B2μ3.(10)P=20000B^2\mu^2, \qquad D_0=320000B^2\mu^3. \tag*{(10)}

The resulting matrix has the row, support, and distance bounds of Theorem 2.

The local code has the following explicit construction. In its notation take d=min⁡(m,D0)d=\min(m,D_0), δ=1/(100Bμ)\delta=1/(100B\mu), and h=⌈δd⌉−1h=\lceil\delta d\rceil-1. If h=0h=0 use no local checks. Otherwise let r=⌈log⁡2d⌉r=\lceil\log_2 d\rceil, choose distinct α1,…,αd∈F2r\alpha_1,\ldots,\alpha_d\in\mathbb{F}_{2^r}, and impose

∑j=1dαjkxj=0in F2r,0≤k<h.(11)\sum_{j=1}^{d}\alpha_j^k x_j=0\quad\text{in }\mathbb{F}_{2^r},\qquad0\le k<h. \tag*{(11)}

We expand each field equation into rr binary equations. Any at most hh columns are independent: their first as many field rows form a square Vandermonde matrix with nonzero determinant. Thus a nonzero binary kernel word has weight at least h+1≥δdh+1\ge\delta d. The binary row count satisfies hr<d/(100B)≤⌈d/(8B)⌉hr<d/(100B)\le\lceil d/(8B)\rceil because r≤μr\le\mu.

A field presentation can be found by enumerating irreducible binary polynomials of degree rr; even trial factoring costs polynomial time in 2r≤2d2^r\le2d. Local-code construction is therefore polynomial in mm.

Lemma 11 constructs the required shifts in polynomial time; its exact conditional-expectation proof is in Appendix § 11. Together with the displayed Vandermonde construction this gives

poly⁡(n+m)time and space.(12)\operatorname{poly}(n+m)\quad\text{time and space.} \tag*{(12)}

Lemma 5 (Exact separation). Let NA(V)N_A(V) be the object polynomial in (9), with HH, PP as in (6) and (10), and with the initial sparse-check matrix of Theorem 2. At most 3H3H additional parity rows, each of support at most PP, suffice to obtain

NA(V)=∑S:G[S] acyclicVn−∣S∣.(13)N_A(V)=\sum_{S:G[S]\ \mathrm{acyclic}}V^{n-|S|}. \tag*{(13)}

The same matrix separates every subfamily obtained by pinning vertices or edges.

Proof. The proof appends parity rows that remove a constant fraction of the surviving violations. A random list ((e1,c1),…,(eP,cP))((e_1,c_1),\ldots,(e_P,c_P)), with uniform edge coordinates and independent coefficient bits, hits the support of each surviving nonzero violation with probability greater than 1/21/2. Conditional on a hit, its row parity is uniform. It therefore rejects each such object with probability at least 1/41/4. If D(A)D(A) is their surviving number, a minimum-count row leaves at most 3D(A)/43D(A)/4. The zero-violation count is independent of the row. After 3H3H rows the remaining number is less than (3/4)3H2H=(27/32)H<1(3/4)^{3H}2^H=(27/32)^H<1, hence zero. Elimination is objectwise and therefore holds for every restricted subfamily and every coefficient. Appendix § 12 constructs these rows using at most 6HP∗m6HP_*m weighted queries, where P∗=min⁡(P,m)P_*=\min(P,m).

Coefficientwise cancellation with whole-edge events

We use the multivariate version of the forest identity (2), originating in Caracciolo et al. [2], equation (13) at t=1t=1, u=−1u=-1. We give each edge factor 1+weQe1+w_eQ_e the six states: empty, or one of the five canonical monomials of weQew_eQ_e. Selected nonempty states are mutually exclusive even when their atom supports are disjoint. An additional classical edge-event port records whether the edge is selected. All selected edge states require zu=zv=1z_u=z_v=1.

For a fixed edge set FF, the signed sum of these choices and of vertex mass choices is the coefficient of ∏e∈Fwe\prod_{e\in F} w_e in the multivariate identity. It is one when FF is acyclic and zero otherwise. This follows coefficientwise, since the original identity allows independent formal weights wew_e. Multiplication by any function of zz and the edge-event vector ff preserves the coefficientwise cancellation. In particular it permits the parity indicators defining (9), arbitrary pins of zz or ff, and the deletion weight.

Integral parity lift and its total order budget

A row of AA gives a parity of terms fef_e and zuzvz_u z_v. Its support has size at most D0D_0 or PP, so it has at most

τ=2max⁡(D0,P)=O(B2μ3)(14)\tau=2\max(D_0,P)=O(B^2\mu^3) \tag*{(14)}

monomials, each of degree at most two. After any pins, remove zero terms, move constants to the right side, and cancel duplicate terms over F2\mathbb{F}_2. The surviving row has the form ⨁jtij=bi\bigoplus_j t_{ij}=b_i, where every tijt_{ij} is a positive predicate fef_e, zvz_v, or zuzvz_u z_v. Its integer indicator is

Ri=1+(−1)bi∏j(1−2tij)2.(15)R_i=\frac{1+(-1)^{b_i}\prod_j(1-2t_{ij})}{2}. \tag*{(15)}

The empty selection has coefficient 1−bi1-b_i; a nonempty selection of kik_i distinct terms has coefficient (−1)bi+ki2ki−1(-1)^{b_i+k_i}2^{k_i-1}. These are integer coefficients; there is no division by two inside Z/2pZ\mathbb{Z}/2^p\mathbb{Z}.

Let a≤6Ha\leq6H be the number of parity rows. A product selection of total order T=∑ikiT=\sum_i k_i has valuation at least T−aT-a. Therefore retain only

T≤K0=p+a−1=H+a.(16)T\leq K_0=p+a-1=H+a. \tag*{(16)}

All other terms vanish coefficientwise modulo 2p2^p, before any Grassmann cancellation or summation over selectors. For a parity predicate fef_e, an edge column requires the whole-edge event to be selected. For zvz_v or zuzvz_u z_v, vertex columns require the indicated selectors. Repeated positive requirements are harmless since the variables are Boolean. Each selected parity term has one or two classical ports.

Explicit ordinary network and degree control

We take J=⌈H1/4⌉J=\lceil H^{1/4}\rceil groups. There are JJ graph-factor rows, JJ parity-factor rows, JJ physical-atom columns, JJ vertex-selector columns, and JJ edge-event columns.

Assign every selected graph monomial to the group containing its smallest physical atom. We partition the aa parity rows into JJ groups with at most ⌈a/J⌉\lceil a/J\rceil rows each. Within the two classical column families, balance the input incidence counts of individual variables greedily.

As before, make a separate port for each physical or classical occurrence, and index selected port subsets per group pair and grade. We enumerate the bucket counts dghcd_{ghc} and additionally the total parity order in each parity group, requiring their sum at most K0K_0. The order of a selection is its number of monomials. The graph-factor entries check all-or-none selection of each monomial and multiply its coefficient. Parity-factor entries additionally check their public orders and multiply the row coefficients in (15). Physical columns require exact atom coverage. Edge columns check that each edge has at most one event, exactly one if pinned to one, no event if pinned to zero, and one whenever a parity term requires it. Vertex columns contribute 1 if the vertex is required to be retained, and 1+V1+V if it is unpinned and unrequired. A pinned deleted vertex contributes VV. Thus a local entry is computable by explicit subset decoding, incidence checks, and polynomial arithmetic.

All physical monomials have even degree. Their complete sign is given by the two local inversion signs and the public phase (4). Classical ports contribute no sign. For every surviving selection there is exactly one count/order array and one set of valid subset indices. Conversely, nonzero entries force precisely an allowed macro/lift selection. Hence the sum of these ordinary contractions is (9) modulo 2p2^p in the ring

(Z/2pZ)[V]/(Vn+1).(17)(\mathbb{Z}/2^p\mathbb{Z})[V]/(V^{n+1}). \tag*{(17)}

There are exactly 2n2n selected physical ports, at most 2n2n graph selector ports, at most nn edge-event ports, and at most 2K02K_0 parity predicate ports. We put K=5n+2K0=O(H)K=5n+2K_0=O(H). The input has I=O(n+m+aτ)I=O(n+m+a\tau) ports. The subset entropy bound gives

M≤O(J2)+Klog⁡2e(I+K)K=O(H[1+log⁡(1+I/H)]).(18)M \le O(J^2)+K\log_2\frac{e(I+K)}{K}=O\left(H[1+\log(1+I/H)]\right). \tag*{(18)}

There are at most (K+1)O(J2)(K+1)^{O(J^2)} public arrays, including the JJ order counters. They can be streamed in polynomial space.

For the degree argument first suppose m≤n33/32m\le n^{33/32}. In the unrestricted oracle network, pin every zvz_v or fef_e with more than H3/4H^{3/4} input incidences, in all ways. There are O(I/H3/4)O(I/H^{3/4}) such variables. Each branch restricts the objects in (7), so the branches sum without multiplicity. A pinned fe=1f_e=1 requires the macro event, and its parity occurrences disappear upon normalization; a pinned fe=0f_e=0 deletes its macro alternatives. An inconsistent edge and vertex pin gives zero. After normalization, the remaining unpinned variables have incidence at most H3/4H^{3/4}. A fixed edge retains only its at most five event ports. Constants and scalar vertex weights cause no additional high-degree node.

The graph row’s selected load is O(n/J)O(n/J): each selected graph monomial consumes its owner atom. Its wire degree is at most O(J+(n/J)log⁡(I+2))O(J+(n/J)\log(I+2)). The same bound holds for physical columns. Each parity row group has raw load O((a/J+1)τ)O((a/J+1)\tau); each balanced classical column has raw load O(I/J+H3/4+1)O(I/J+H^{3/4}+1). For any bucket, ⌈log⁡2(Nd)⌉≤N\lceil\log_2 \binom{N}{d}\rceil\le N, so raw load bounds wire degree where needed. Using B=O(n1/32)B=O(n^{1/32}), μ=O(log⁡n)\mu=O(\log n), H=O(nlog⁡n)H=O(n\log n) gives

I=O(n17/16(log⁡(n+2))4),#pinned variables=O(n5/16(log⁡(n+2))4),Δ=O(n13/16(log⁡(n+2))4).(19)\begin{aligned} I&=O(n^{17/16}(\log(n+2))^4),\\ \#\text{pinned variables}&=O(n^{5/16}(\log(n+2))^4),\\ \Delta&=O(n^{13/16}(\log(n+2))^4). \tag*{(19)} \end{aligned}

These loose polynomial logarithmic factors suffice: 13/16<9/1013/16<9/10. For sufficiently large nn the maximum degree is below the source threshold at the root scale below. Bounded exceptional input sizes can be handled by direct enumeration.

The weighted moments used to choose the separating rows have the same root scale. Lemma 12, proved in Appendix § 12, includes their precision, incidence, and local-entry costs.

Theorem 6 (Density-sensitive complete feedback vertex counting). Assuming Hypothesis 1, all feedback vertex set cardinality counts of a simple nn-vertex, mm-edge graph can be computed deterministically in polynomial space and time

poly⁡(n+m)2O(nL[L+log⁡log⁡(n+4)]log⁡(n+2)),L=1+log⁡2(1+m/n).(20)\operatorname{poly}(n+m)2^{O\left(\frac{nL[L+\log\log(n+4)]}{\sqrt{\log(n+2)}}\right)},\qquad L=1+\log_2(1+m/n). \tag*{(20)}

The same bound includes a minimum deletion set and unranking any deletion set of specified cardinality. Direct 2npoly⁡(n+m)2^n\operatorname{poly}(n+m) enumeration is an additional alternative, so one may take the faster of these two bounds.

Proof. The proof checks the contraction hypotheses at the compressed scale and then recovers the integer coefficients. Edgeless instances use the direct polynomial at the start of this section, including pinned calls during recovery. Assume henceforth that m≥1m\ge1. For m≤n33/32m\le n^{33/32}, (18) is bounded by a constant times

s=nL[L+log⁡log⁡(n+4)],(21)s=nL[L+\log\log(n+4)], \tag*{(21)}

since log⁡(1+I/H)=O(L+log⁡log⁡(n+4))\log(1+I/H)=O(L+\log\log(n+4)). We choose an integer scale that is a sufficiently large constant multiple of (21). The network has O(s)O(s) wires, maximum degree at most s9/10s^{9/10}, polynomial-size descriptions and polynomial-time local entries. The coefficient precision p=H+1p=H+1 and truncation length n+1n+1 are both O(s)O(s). Hypothesis 1 applies to (17). For these unweighted calls, arrays and pin branches are enumerated sequentially. Their exponents, O(Hlog⁡(H+2))O(\sqrt{H}\log(H+2)) and O(n5/16log⁡4(n+2))O(n^{5/16}\log^4(n+2)), are absorbed in O(s/log⁡(n+2))O(s/\sqrt{\log(n+2)}). The initial code cost (12) is polynomial. We use the polynomial-query selection of Section C; Lemma 12 charges every weighted moment at the same scale, including discarded candidates. For the unweighted calls, counts used in comparisons are exact integers: the residue of N(A)N(A) is less than 2H<2p2^H<2^p by (8). After separation a final polynomial-valued count gives (13), coefficientwise without an interpolation loss. Its least nonnegative coefficients are the desired integers.

If m>n33/32m > n^{33/32}, then L>log⁡2(n)/32L > \log_2(n)/32 and the exponent in (20) dominates nn for sufficiently large nn. Direct enumeration of vertex sets and a forest test therefore proves the same displayed bound throughout the dense range.

For recovery, find the least nonzero cardinality coefficient. Process vertices in order and count that coefficient with the next vertex pinned deleted. We retain that branch when nonzero, or use the other branch; for unranking subtract its count when proceeding to the other branch. The same completed separating matrix works for all prefix restrictions by the lemma. There are O(n)O(n) further oracle calls, with the original budgets retained as upper bounds. Computing arbitrary-rank solutions at a prescribed cardinality is identical. Streaming successive ranks gives enumeration with this delay and polynomial working space, in addition to unavoidable output cost.

All-density feedback vertex counting by disjoint sparsification

Induced forests admit a disjoint sparsification because their selected graphs have small average degree. High-degree guessing and branching are used for induced sparse-subgraph optimization by Novotná et al. [7]. The counting reduction below fixes every selected neighbor in a retaining branch, imposes residual degree caps, and recovers the multiplicity of exceptional-set guesses by binomial inversion.

Degree-capped forest objects

Let RR be a graph on NN vertices with a set BB pinned retained. We require deg⁡R[S](v)≤t\deg_{R[S]}(v) \le t for every retained v∉Bv \notin B. In the intermediate object set (7), impose instead

deg⁡F(v)≤t(v∉B).(22)\deg_F(v) \le t \qquad(v \notin B). \tag*{(22)}

After separation F=E(R[S])F = E(R[S]), so (22) is exactly the required induced-degree condition. The object set is still nonnegative, still has the bound (8), and the source greedy separation applies to this restricted family without change.

The network implementation counts whole-edge incidences at the vertex columns. Mark a macro-edge selector port as a degree event, distinguishing it from positive selector requirements coming from a parity monomial. A selected macro edge contributes one event at each endpoint even if its Grassmann monomial uses atoms at only one endpoint. The column tensor assigns zero to an assignment exceeding its cap. For a capped vertex already pinned to one, keep these event ports; the degree event remains after the selector is pinned. Coefficientwise cancellation for a fixed FF remains valid, because its degree is independent of which of the five macro monomials was selected.

We use this extension only at leaves where every capped vertex has input degree at most DD, with DD a fixed power of the logarithm of the original size. The extension adds no ports beyond the existing at most two graph-selector ports per macro edge. After high-incidence selector pins, at most 5D5D graph-event occurrences remain at a capped vertex; its parity occurrences disappear upon normalization. Thus the classical column load bound becomes

O(I/J+H3/4+D).(23)O(I/J + H^{3/4} + D). \tag*{(23)}

For leaf size comparable to the original size up to a logarithmic factor, DD is polylogarithmic in the leaf size. All wire, selected load, precision, and degree estimates from § 5 therefore continue to hold.

Disjoint reduction for a fixed exceptional set

We fix integers 2≤t<D2 \le t < D and set

b=min⁡(n,⌊2(n−1)t+1⌋).(24)b = \min\left(n,\left\lfloor\frac{2(n-1)}{t+1}\right\rfloor\right). \tag*{(24)}

Every forest induced on SS has at most bb vertices of degree greater than tt, since its degree sum is at most 2(n−1)2(n-1). Denote this set by Ht(S)H_t(S). We enumerate all sets B⊆V(G)B \subseteq V(G) of size at most bb. For fixed BB, the subproblem counts

B⊆S,G[S] acyclic,Ht(S)⊆B,(25)B \subseteq S,\qquad G[S]\text{ acyclic},\qquad H_t(S) \subseteq B, \tag*{(25)}

with any additional original selector pins. If G[B]G[B] has a cycle or a vertex of BB is pinned deleted, this count is zero.

Maintain an active induced graph R=G[W]R = G[W] and a set P⊆WP \subseteq W of vertices pinned retained, initially including BB and the original retained pins. Deleted pins are removed from WW. If there is v∈W∖Bv \in W \setminus B of current degree dR(v)>Dd_R(v) > D, proceed as follows. If v∉Pv \notin P, create one branch deleting vv. For every possible exact selected-neighbor set

T⊆NR(v),∣T∣≤t,NR(v)∩P⊆T,(26)T \subseteq N_R(v),\qquad|T| \le t,\qquad N_R(v) \cap P \subseteq T, \tag*{(26)}

create a branch retaining vv, pinning every vertex of TT retained, and deleting every vertex of NR(v)∖TN_R(v) \setminus T. If (26) has no solution, there is no retaining branch. We use a deterministic rule to choose vv.

Lemma 7 (Disjoint leaves and their density). Fix integers 2≤t<D2 \le t < D and an exceptional retained set BB as in (25). The exact-neighbour branching procedure of this section partitions the solutions of (25) among its leaves, with multiplicity one. At a leaf, each vertex outside BB has input degree at most DD and the number of edges is at most NDND, where N=∣W∣N = |W|. Its solutions are exactly the pinned induced forests with degree cap tt on W∖BW \setminus B. The number of leaves is at most

2O((n/(D−t)+1)(t+2)log⁡(n+2)).(27)2^{O((n/(D-t)+1)(t+2)\log(n+2))}. \tag*{(27)}

The leaves can be streamed with polynomial working space.

Proof. A solution either omits vv or retains it. In the latter case, NR(v)∩SN_R(v) \cap S is its unique valid set TT in (26), because v∉Bv \notin B has degree at most tt in the final induced graph. Pinning both vv and TT makes distinct retaining branches disjoint. Future deletions cannot undo these pins. Conversely, every leaf solution extends to an original solution by declaring removed vertices deleted. The partition follows by induction.

A retaining branch deletes at least dR(v)−t>D−td_R(v)-t > D-t active vertices; none is already pinned retained by (26). There can be at most n/(D−t)n/(D-t) such steps on a path, while every path has at most nn steps in total. Each retaining step has at most (n+1)t+1(n+1)^{t+1} choices. Encoding the positions of these steps and their choices proves the loose bound (27), including paths ending in an empty subproblem. Graph and pin descriptions along a depth-first path occupy polynomial space; no family of leaves is stored.

At termination, degrees outside BB are at most DD in the whole active graph, including neighbors in BB. Edges with an endpoint outside BB number at most (N−∣B∣)D(N-|B|)D. Edges entirely in BB number at most ∣B∣−1|B|-1 when BB is nonempty, since G[B]G[B] was checked acyclic. For B=∅B=\varnothing the simpler bound ND/2ND/2 applies. Both imply ∣E(R)∣≤ND|E(R)| \le ND. The cap in (22) enforces every remaining condition of (25). □

Removing multiplicities between exceptional sets

Different BB can still represent the same induced forest. Let Nj,hN_{j,h} be the number of original induced forests with jj retained vertices and exactly hh vertices of degree greater than tt. For 0≤k≤b0 \le k \le b, sum the leaf counts for all kk-element BB, and let cj,kc_{j,k} be their number of jj-vertex solutions. For a fixed solution SS with ∣S∣=j|S|=j and ∣Ht(S)∣=h|H_t(S)|=h, its admissible guesses are exactly the sets Ht(S)⊆B⊆SH_t(S) \subseteq B \subseteq S of size kk. Therefore

cj,k=∑h=0kNj,h(j−hk−h).(28)c_{j,k}=\sum_{h=0}^{k}N_{j,h}\binom{j-h}{k-h}. \tag*{(28)}

Terms with impossible sizes are zero. For each jj, recover in order

Nj,0=cj,0,N_{j,0}=c_{j,0},
Nj,h=cj,h−∑r=0h−1Nj,r(j−rh−r)(1≤h≤min⁡(b,j)).(29)N_{j,h}=c_{j,h}-\sum_{r=0}^{h-1}N_{j,r}\binom{j-r}{h-r}\qquad(1\le h\le\min(b,j)). \tag*{(29)}

The total number of induced forests of size jj is ∑h=0min⁡(b,j)Nj,h\sum_{h=0}^{\min(b,j)}N_{j,h}, since every such forest has h≤bh\le b. The triangular matrix in (28) has diagonal one, so no division or precision loss occurs. Moreover cj,k≤2n(nk)≤22nc_{j,k}\le2^n\binom{n}{k}\le2^{2n}; all reconstruction and accumulation use polynomially many bits. Original selector pins preserve (28), because for each surviving SS all of its admissible BB are still enumerated.

Proof of Theorem 1. The proof combines the sparse leaf cost with the exceptional-set and branch counts. Let λ=⌈log⁡2(n+2)⌉\lambda=\lceil\log_2(n+2)\rceil, choose t=t= max(2,⌈λ⌉)(2, \lceil\sqrt{\lambda}\rceil) and D=t+λ2D=t+\lambda^2. For sufficiently large nn, (24) gives b=O(n/λ)b=O(n/\sqrt{\lambda}). The number of exceptional guesses is bounded by

∑k=0b(nk)=2O(nlog⁡λ/λ).(30)\sum_{k=0}^{b}\binom{n}{k}=2^{O(n\log\lambda/\sqrt{\lambda})}. \tag*{(30)}

For each guess, (27) gives 2O(n/λ)2^{O(n/\sqrt{\lambda})} leaves; the additive (t+2)log⁡(n+2)=O(λ3/2)(t+2)\log(n+2)=O(\lambda^{3/2}) is absorbed for sufficiently large nn. Neither bound assumes the input sparse.

If a leaf has N≤n/λN\le n/\lambda vertices, enumerate its subsets and check forest membership, pins, and degree caps directly. This costs 2O(n/λ)poly⁡(n+m)2^{O(n/\lambda)}\operatorname{poly}(n+m). Otherwise log⁡N=Θ(log⁡n)\log N=\Theta(\log n), and the density bound ∣E(R)∣≤ND|E(R)|\le ND gives LR=O(log⁡λ)L_R=O(\log\lambda). The capped extension (23) applies: D=O((log⁡N)2)D=O((\log N)^2), so the residual event load at every pinned capped vertex is below H3/4H^{3/4} for sufficiently large NN. Edgeless leaves use the direct base case of § 5. For the other leaves, we use Theorem 6 on the capped object family. Its cost is

poly⁡(n+m)2O(N(log⁡λ)2/log⁡N)≤poly⁡(n+m)2O(n(log⁡λ)2/λ).(31)\operatorname{poly}(n+m)2^{O(N(\log\lambda)^2/\sqrt{\log N})}\le\operatorname{poly}(n+m)2^{O(n(\log\lambda)^2/\sqrt{\lambda})}. \tag*{(31)}

All initial parity-matrix construction, greedy candidates, high-incidence pins, count/order arrays, and integer recovery are already included in this leaf bound. Multiplying by (30) and the number of leaves preserves (1). Handle bounded exceptional sizes directly.

Accumulate cj,kc_{j,k} sequentially, using the original retained size j=N−j=N- leaf deletion size; vertices removed before the leaf are deleted and contribute no retained vertices. We apply (29) and reverse the cardinality index to get feedback vertex counts. Streaming guesses, branches, and leaf counters keeps polynomial space.

For recovery, find the first nonzero deletion-size count. We fix vertices successively, count the branch deleting the next vertex, and choose or skip that branch according to the desired rank. Arbitrary original pins are supported by the same proof. There are O(n)O(n) invocations of the whole counter per recovered set, preserving (1). Repeating for successive ranks gives the stated enumeration bound.

Components, induced trees, and induced paths

The forest identity can retain a component marker TT while using VV for deletions. At a vertex use mass 1+(T−1)zv1+(T-1)z_v and at an edge use (ψˉu−ψˉv)(ψu−ψv)−Tτuτv(\bar{\psi}_u-\bar{\psi}_v)(\psi_u-\psi_v)-T\tau_u\tau_v. Deleted isolated vertices then have mass one. The separated polynomial is

∑S:G[S] forestTc(G[S])Vn−∣S∣.\sum_{S:G[S]\ \mathrm{forest}} T^{c(G[S])}V^{n-|S|}.

For an NN-vertex leaf, evaluating T=0,…,NT=0,\ldots,N at NN additional bits of precision recovers all component coefficients by finite differences. The construction and precision proof appear in Appendix § 13.

Theorem 8 (All-density size–component counts). Under the Hypothesis 1, for an arbitrary simple graph all integers

Cd,c=#{S⊆V(G):∣V(G)∖S∣=d, G[S] a forest, c(G[S])=c}(32)C_{d,c} = \#\{S \subseteq V(G) : |V(G) \setminus S| = d,\ G[S]\ \text{a forest},\ c(G[S]) = c\} \tag*{(32)}

can be computed deterministically in polynomial space and time

poly⁡(n+m)2O(n(log⁡log⁡(n+4))2/log⁡(n+2)).(33)\operatorname{poly}(n+m)2^{O\left(n(\log\log(n+4))^2/\sqrt{\log(n+2)}\right)}. \tag*{(33)}

Arbitrary original selector pins are allowed. A set with prescribed size and component count can be recovered or unranked within the same bound; all such sets can be streamed with this delay.

Proof. We use the marked counter at each disjoint leaf. The binomial inversion is applied independently at each component count. Appendix D gives the local mass events, degree and precision bounds, and recovery proof.

Corollary 9 (Induced trees and induced paths). Assuming Hypothesis 1, all size counts of induced trees and of induced paths in an arbitrary simple graph, as well as a largest such object, can be computed deterministically within (33) and polynomial space. This includes containment of specified vertices, exclusion of specified vertices, exact integer recovery and unranking. Induced paths are counted by vertex set, with no orientation multiplicity.

Proof. For trees select c=1c = 1 in (32); a single retained vertex is a tree, while the empty set has c=0c = 0 and is excluded. For paths impose degree cap two on every retained vertex. In this case the exceptional set is known to be empty: use the disjoint branching directly with t=2t = 2 and D=2+λ2D = 2 + \lambda^{2}. Its leaf cost and branch bound are within (33), and every remaining input vertex has degree at most DD. The capped marked counter with c=1c = 1 counts exactly connected acyclic graphs of maximum degree two, namely paths including a single vertex. Selecting the largest nonzero size gives deterministic optimization. Prefix-pin counts recover the original vertex set; tracing from either endpoint provides its path order. Prescribed vertices are ordinary pins.

Sparse companion counts

The same subset-index encoding supports directed Hamilton cycles, edge-cardinality counts of unrooted spanning forests, and vertex-cardinality counts of Steiner edge trees. We put s=n(1+log⁡2(1+m/n))s = n(1 + \log_{2}(1 + m/n)).

Corollary 10. Assuming Hypothesis 1, these three counting problems admit deterministic algorithms in poly⁡(n+m)2O(s/log⁡(s+2))\operatorname{poly}(n+m)2^{O(s/\sqrt{\log(s+2)})} time and polynomial space. Hamilton and minimum Steiner witnesses can be recovered in the same bound. Steiner counts support selector pins, forbidden edges, and required forest edges. For fixed CC and m/n≤(log⁡n)Cm/n \le(\log n)^C, the time is poly⁡(n+m)2O(nlog⁡log⁡n/log⁡n)\operatorname{poly}(n+m)2^{O(n\log\log n/\sqrt{\log n})}.

Proof. Appendix E gives the signed Hamilton identity, forest coefficient recovery, and the selected-vertex Steiner polynomial, together with all degree, precision, and recovery bounds.

Open problems

The all-density reduction uses the sparsity of each retained induced forest. Obtaining a vertex-subexponential bound for Hamilton counting on dense graphs calls for a different density reduction. Exact counting of general connected vertex sets is a second question, because cyclic selected graphs introduce spanning-tree multiplicities. Within the present construction, reducing the iterated-logarithm loss requires tighter filtering or encoding budgets.

AI assistance

OpenAI Codex was used to assist with drafting and revising the manuscript, developing parts of the mathematical arguments, and checking derivations.

Exact coefficient recovery

Coefficient recovery without a large formal coefficient ring

Let f(X)f(X) have integer coefficients and degree at most DD. Values at 0,…,D0,\ldots,D modulo 2p+D2^{p+D} determine all its power coefficients modulo 2p2^p. Indeed,

f(X)=∑j=0DΔjf(0)j!X(X−1)⋯(X−j+1)(34)f(X)=\sum_{j=0}^{D}\frac{\Delta^j f(0)}{j!}X(X-1)\cdots(X-j+1) \tag*{(34)}

and Δjf(0)\Delta^j f(0) is divisible by j!j! for an integer-coefficient polynomial. Removing 2v2(j!)2^{v_2(j!)}, then inverting the odd part of j!j! modulo 2p2^p, is valid because v2(j!)≤Dv_2(j!)\le D.

For separate degrees D1,D2D_1,D_2, apply this procedure successively using precision p+D1+D2p+D_1+D_2 at the evaluation grid. Only polynomially many scalar contractions are used.

Constructing the sparse-check shifts

Lemma 11 (Polynomial-time shift construction). Let q=2ℓ≥2q=2^\ell\ge2, a≥2a\ge2 be an integer, μ≥max⁡(1,ℓ)\mu\ge\max(1,\ell), and d≥8a2μd\ge8a^2\mu. A deterministic algorithm constructs s1,…,sd∈F2ℓs_1,\ldots,s_d\in\mathbb{F}_2^\ell such that, for every nonzero bb,

∣∑j=1d(−1)b⋅sj∣<d/a.\left|\sum_{j=1}^{d}(-1)^{b\cdot s_j}\right|<d/a.

Its bit complexity and space are polynomial in q,d,aq,d,a. For the parameters of source Lemma 6.1, this replaces the exhaustive shift search by polynomial time in mm without changing its row, support, or distance bounds.

Proof. This is an explicit conditional-expectation construction, using a standard derandomization method [9]; efficient small-bias spaces are classical [6]. The following argument specifies the constants and exact arithmetic at this interface.

We put ϵ=1/a\epsilon=1/a, r=1+ϵr=1+\epsilon, and K=(r+r−1)/2K=(r+r^{-1})/2. After jj choices let Sb=∑i≤j(−1)b⋅siS_b=\sum_{i\le j}(-1)^{b\cdot s_i} and

Φj=∑b≠0(rSb+r−Sb).\Phi_j=\sum_{b\ne0}\left(r^{S_b}+r^{-S_b}\right).

For uniform next shift ss, each nonzero character is balanced. Therefore the average next potential is KΦjK\Phi_j. Choosing a shift that minimizes it gives Φd≤2(q−1)Kd\Phi_d\le2(q-1)K^d. For 0<ϵ≤1/20<\epsilon\le1/2,

log⁡K≤ϵ2/2,log⁡r≥ϵ−ϵ2/2,ϵlog⁡r−log⁡K≥ϵ2/4.\log K\le\epsilon^2/2,\qquad\log r\ge\epsilon-\epsilon^2/2,\qquad\epsilon\log r-\log K\ge\epsilon^2/4.

Here logarithms are natural. Moreover log⁡(2(q−1))<(μ+1)log⁡2≤2μlog⁡2<2μ\log(2(q-1))<(\mu+1)\log2\le2\mu\log2<2\mu and dϵ2/4≥2μd\epsilon^2/4\ge2\mu. Consequently 2(q−1)Kd<rϵd2(q-1)K^d<r^{\epsilon d}. If any ∣Sb∣≥ϵd|S_b|\ge\epsilon d, its term alone is at least rϵdr^{\epsilon d}, a contradiction.

No real arithmetic or approximate comparison is needed. At step jj store the two integers

Wb+=[a(a+1)]jr−Sb,Wb−=[a(a+1)]jrSb.W_b^+ = [a(a+1)]^j r^{-S_b}, \qquad W_b^- = [a(a+1)]^j r^{S_b}.

Their exponents of aa and a+1a+1 are j∓Sbj \mp S_b, hence nonnegative. Initially both are one. We write A=(a+1)2A=(a+1)^2, C=a2C=a^2. A positive character multiplies (Wb+,Wb−)(W_b^+,W_b^-) by (A,C)(A,C), and a negative character by (C,A)(C,A). Minimizing the next potential is equivalent to minimizing

∑b≠0(−1)b⋅s(Wb+−Wb−).\sum_{b\ne0}(-1)^{b\cdot s}(W_b^+ - W_b^-).

All qq scores are the Walsh transform of the difference vector, with zero at character zero. A fast exact transform uses O(qlog⁡q)O(q\log q) integer additions per chosen shift. The stored integers have O(dlog⁡(a+1))O(d\log(a+1)) bits; there are O(q)O(q) of them, and updates multiply by integers of O(log⁡(a+1))O(\log(a+1)) bits. All operations have polynomial bit complexity and space, including the output list.

At the source interface set a=200Bμa=200B\mu, d=min⁡(m,320000B2μ3)d=\min(m,320000B^2\mu^3), and take the least power of two qq with qd≥mqd\ge m. If q=1q=1, every shift is zero and there is no nonzero character to constrain. Otherwise d=320000B2μ3=8a2μd=320000B^2\mu^3=8a^2\mu, q≤m<2μq\le m<2^\mu, and qd<2mqd<2m. Thus all assumptions hold. In this nontrivial case d,q≤md,q\le m and aa is polynomial in mm, so the construction is polynomial in mm. Its bias is stronger than the source’s required 1/(200Bμ)1/(200B\mu). The mixing and shortening argument then gives the stated support and distance bounds.

Polynomial-query selection by weighted conditional expectation

Weighted conditional expectations construct each separating row one position at a time.

We set P∗=min⁡(P,m)P_*=\min(P,m). Every nonzero violation surviving the initial matrix has weight at least m/P∗m/P_*. For P≤mP\le m this is the source distance bound; for P>mP>m it follows from its integer weight being at least one. Thus a random length-P∗P_* list still rejects every such violation with probability at least 1/41/4.

For current rows AA, prefix row hh, and 0≤r≤P∗0\le r\le P_*, define the nonnegative integer moment

Wr(A;h)=∑(S,F)∈Ω′Av=0, h⋅v=0(m−∣v∣)r,Wr(A)=∑(S,F)∈Ω′Av=0(m−∣v∣)r.(35)W_r(A;h)=\sum_{\substack{(S,F)\in\Omega'\\ Av=0,\ h\cdot v=0}}(m-|v|)^r, \qquad W_r(A)=\sum_{\substack{(S,F)\in\Omega'\\ Av=0}}(m-|v|)^r. \tag*{(35)}

The pinned and degree-capped object family Ω′\Omega' is permitted, and 00=10^0=1. The weight counts ordered rr-tuples of coordinates at which ve=0v_e=0, giving a direct nonnegative counting interpretation. If rr random list positions remain, the expected number accepted by the final appended row is exactly

Er(A,h)=N(A)2+2Wr(A;h)−Wr(A)2mr.(36)\mathcal{E}_r(A,h)=\frac{N(A)}{2}+\frac{2W_r(A;h)-W_r(A)}{2m^r}. \tag*{(36)}

Indeed a random position (e,c)(e,c) has character expectation 1−∣v∣/m1-|v|/m, and the positions are independent. Expanding the indicator [h⋅v=0]=(1+(−1)h⋅v)/2[h\cdot v=0]=(1+(-1)^{h\cdot v})/2 proves (36).

At the next position enumerate only its 2m2m choices. For each h′=h+ceeh'=h+ce_e compute Wr−1(A;h′)W_{r-1}(A;h') and choose a minimum. All other terms in (36) are common to these children. This therefore minimizes their conditional expectation, without computing any rational number or requiring the unknown zero-violation count. Iterating for P∗P_* positions yields a row at least as good as the initial random-list expectation. Repeating at most 3H3H times gives exact separation by the same (3/4)3H2H<1(3/4)^{3H}2^H<1 argument as before. There are at most 6HP∗m6HP_*m weighted oracle calls, plus an initial unweighted count if early stopping is used. The last-position moment has r=0r=0 and is already the unweighted count of the chosen row.

Lemma 12 (Weighted ordinary-network oracle). For m≤n33/32m\le n^{33/32} and sufficiently large nn, put L=1+log⁡2(1+m/n)L=1+\log_2(1+m/n). Every weighted moment Wr(A;h)W_r(A;h) or Wr(A)W_r(A) in (35), for 0≤r≤P∗0\le r\le P_* and for the pinned, degree-capped object family specified there, has an ordinary scalar-network representation with the same asymptotic root scale s=nL[L+log⁡log⁡(n+4)]s=nL[L+\log\log(n+4)] as (21). Its complete evaluation cost under D.1, including public arrays and heavy-variable pins, is poly⁡(n+m)2O(s/log⁡(n+2))\operatorname{poly}(n+m)2^{O(s/\sqrt{\log(n+2)})} with polynomial working space. Consequently the separating rows require polynomially many weighted calls within (20).

Proof. The weighted oracle encodes the moment as labeled selector slots while preserving whole-edge cancellation. In every object, F⊆E(G[S])F\subseteq E(G[S]). The integer violation weight is therefore ∣v∣=∑uv∈Ezuzv−∑efe|v|=\sum_{uv\in E}z_uz_v-\sum_e f_e. We add the factor

Q(z,f)r=(m−∑uv∈Ezuzv+∑efe)r.(37)Q(z,f)^r=\left(m-\sum_{uv\in E}z_uz_v+\sum_e f_e\right)^r. \tag*{(37)}

It is a function only of selectors and whole-edge events, so it preserves the coefficientwise forest cancellation. On genuine objects it equals (m−∣v∣)r≥0(m-|v|)^r\ge0. The prefix row hh is represented by one ordinary parity lift, in exactly the same way as any candidate row. Throughout the selection process the total parity row count is at most 6H6H and its support bounds remain D0D_0 and P∗P_*.

We represent (37) by rr labeled slots. Each slot chooses the constant mm, one term −zuzv-z_uz_v, or one term +fe+f_e. Constant choices have no ports; other choices have at most two classical predicate ports and no physical atoms or degree events. We put all slots in one additional factor row. Its entry checks that a slot selects either no term or exactly one complete term, and multiplies the resulting coefficients. Classical columns enforce all positive predicates. After pins, collect constant terms within each slot and delete or shorten the remaining predicates; this does not increase incidence. Distinct slots retain their labels, so all ordered products in QrQ^r occur with their correct multiplicities. This moment polynomial is over the integers: duplicate predicates retain their integer multiplicities. The moment row uses the subset-index encoding of § 4.

We use precision

P0=H+P∗μ+2.P_0=H+P_*\mu+2.

Every required nonnegative count is less than 2Hmr<2P02^{H}m^{r}<2^{P_0}. Thus the least nonnegative residue is the exact integer used in the comparison. The parity-lift order cutoff must be recomputed as P0+a−1P_0+a-1, where aa is the current row count. For the stated density range, B=O(n1/32)B=O(n^{1/32}), hence P∗μ=O(n1/16log⁡3(n+2))=o(n)P_*\mu=O(n^{1/16}\log^3(n+2))=o(n) and P0=O(H)P_0=O(H). There are only 2r=o(H)2r=o(H) additional selected ports. The original O(H)O(H) selected-port and precision budgets are preserved.

Raw incidence is now

I′=O(n+m+Hτ+P∗m)=O(n35/32log⁡4(n+2)).I'=O(n+m+H\tau+P_*m)=O(n^{35/32}\log^4(n+2)).

The subset entropy bound still gives O(H[1+log⁡(1+I′/H)])=O(s)O(H[1+\log(1+I'/H)])=O(s) wires, since log⁡(1+I′/H)=O(L+log⁡log⁡(n+4))\log(1+I'/H)=O(L+\log\log(n+4)). With the same J=⌈H1/4⌉J=\lceil H^{1/4}\rceil groups, the additional row has wire degree O(J+P∗log⁡(I′+2))O(J+P_*\log(I'+2)) by its selected-port bound. We pin variables of incidence greater than H3/4H^{3/4} and rebalance the classical columns as before. The number of pinned variables and the maximum remaining degree are bounded respectively by

O(n11/32log⁡4(n+2)),O(n27/32log⁡4(n+2)).(38)O(n^{11/32}\log^4(n+2)),\qquad O(n^{27/32}\log^4(n+2)). \tag*{(38)}

For capped FVS leaves, add the same O(D)O(D) residual event load from (23); DD is polylogarithmic and is absorbed. Since 27/32<9/1027/32<9/10, the degree condition of Theorem D.1 holds for sufficiently large nn. The extra factor row adds O(J)O(J) buckets, so the array exponent is O(Hlog⁡(H+2))O(\sqrt{H}\log(H+2)). Both this exponent and the pin-branch exponent in (38) are absorbed by O(s/log⁡n)O(s/\sqrt{\log n}). All local entries, including constant powers and invalid-index checks, are computable in polynomial bit complexity and space.

The number of moments is polynomial in n+mn+m, each is evaluated sequentially, and their descriptions have polynomial length. The oracle and selection costs follow. Small sizes and the denser regime retain the direct-enumeration treatment of Theorem 6.

Component markers and recovery

The counter in § 6 can retain the exact number of components without increasing its main exponent. The component variable is already present in the forest identity of Caracciolo et al. [2], equation (13). The component-counting interface must ensure that deleted isolated vertices contribute no component marker, and must recover two statistics using the source’s permitted single-variable coefficient ring.

Marked mass choices with deleted vertices removed

We write TT for the component marker and VV for the deletion marker. For a fixed selector vector zz with retained set SS, put

av(T,z)=1+(T−1)zv,Qe(T)=(ψˉu−ψˉv)(ψu−ψv)−Tτuτv.(39)a_v(T,z)=1+(T-1)z_v,\qquad Q_e(T)=(\bar{\psi}_u-\bar{\psi}_v)(\psi_u-\psi_v)-T\tau_u\tau_v. \tag*{(39)}

The multivariate identity is

Top∏v(1+av(T,z)τv)∏e=uv(1+wezuzvQe(T))=∑F⊆E(S), F acyclicT∣S∣−∣F∣∏e∈Fwe(40)\mathop{\mathrm{Top}}\prod_v(1+a_v(T,z)\tau_v)\prod_{e=uv}(1+w_ez_uz_vQ_e(T))=\sum_{\substack{F\subseteq E(S),\ F\ \mathrm{acyclic}}}T^{|S|-|F|}\prod_{e\in F}w_e \tag*{(40)}

Indeed, after fixing zz, deleted vertices have no incident edge terms and their mass integral is one. On SS, source equation (13) has uniform parameters t=Tt=T, u=−Tu=-T, hence one factor TT per forest component. Thus (40) follows over the integers coefficientwise in the independent edge variables. It also holds for S=∅S=\varnothing, whose component exponent is zero.

We keep the whole-edge macro convention of Section 5. We multiply each quartic edge monomial’s coefficient by TT. For a mass term at a pinned retained vertex, multiply its coefficient by TT; at a pinned deleted vertex, leave the coefficient one. A mass term at an unpinned vertex sends one additional mass-choice event to that vertex’s classical column. The event records selection of a mass monomial. It is defined for every selector value, and degree caps count the separate edge events.

Let gvg_v record whether that mass term was selected. An unpinned vertex required retained by an edge macro or parity predicate contributes TgvT^{g_v} at its column. If it has no such requirement, its column sums the two choices with factor

V+Tgv.(41)V+T^{g_v}. \tag*{(41)}

Pinned deleted vertices contribute VV as before. Every nonzero full assignment has exact physical-atom coverage. Consequently a vertex without its mass term is incident to a selected edge term and is required retained; the apparently unrestricted alternative in (41) cannot create a spurious deleted vertex in that case. This describes polynomial-time entries using only the ports already incident to their row or column.

There are at most NN additional selected mass-event ports on an NN-vertex leaf. The total selected-port bound becomes 6N+2K0=O(H)6N+2K_0=O(H), and input incidence increases by at most NN. Each mass term still consumes its owner atom, so the graph-row bound has the same bound. Each free selector column receives one mass occurrence; pinned selectors have fixed mass values. The degree caps count edge events. The sign calculation and degree bounds are those of Sections 5 and 6.

For a parity matrix AA, the resulting polynomial is exactly

FA(T,V)=∑(S,F)∈Ω′:Av(S,F)=0T∣S∣−∣F∣VN−∣S∣(42)F_A(T,V)=\sum_{\substack{(S,F)\in\Omega':\\ A v(S,F)=0}}T^{|S|-|F|}V^{N-|S|} \tag*{(42)}

where Ω′\Omega' includes the current pins and degree caps. The greedy separation of Lemma 5 is applied at T=1T=1, V=1V=1. Its completed matrix rejects every incorrect object, independently of T,VT,V. Hence its final polynomial is

FA(T,V)=∑S: G[S] forest,pins/caps satisfiedTc(G[S])VN−∣S∣(43)F_A(T,V)=\sum_{\substack{S:\ G[S]\ \mathrm{forest},\\ \mathrm{pins/caps\ satisfied}}}T^{c(G[S])}V^{N-|S|} \tag*{(43)}

The same separating matrix serves every component value.

Two statistics with one formal variable

The degree in TT is at most NN even before cancellation in the signed-cover expansion. Every selected mass contributes at most one TT and consumes two physical atoms; every quartic edge contributes one TT and consumes four. There are only 2N2N atoms. The deletion degree is also at most NN.

Let p=H+1p = H + 1, with HH defined for the leaf as in (6). For each integer i=0,…,Ni = 0, \ldots, N, contract the marked network at T=iT = i over

(Z/2p+NZ)[V]/(VN+1).(44)(\mathbb{Z}/2^{p+N}\mathbb{Z})[V]/(V^{N+1}). \tag*{(44)}

The lifted parity truncation uses this increased precision, so its total retained order is p+N+a−1=O(H)p+N+a-1 = O(H). Both the precision and the one formal truncation length remain O(s)O(s) at the source root scale. Local entries compute powers of ii modulo 2p+N2^{p+N}, using p+Np+N bits of precision.

For each deletion coefficient dd, apply the integer-polynomial Newton recovery (34) to [Vd]FA(T,V)[V^d]F_A(T,V). Its degree is at most NN, and the jjth difference is divisible by j!j!. Removing the power of two in j!j! loses at most NN bits, and the odd factor is invertible. Thus the values modulo 2p+N2^{p+N} determine every power coefficient modulo 2p2^p. All final coefficients count vertex sets and are at most 2N<2p2^N < 2^p, so their least nonnegative residues are the exact integers.

Only N+1N+1 contractions are used, each in the source’s permitted single-variable ring. The value table and coefficient table require polynomial space.

Proof details for Theorem 8.

Proof. We apply the same exceptional-set guesses and disjoint sparse branches as Theorem 1. At each leaf compute (43) using (44), or directly enumerate if the leaf is small. This adds only a polynomial number of source contractions at the same scale. Vertices removed before reaching a leaf are deleted, so the retained size is N−dleafN-d_{\mathrm{leaf}} and its component count is exactly the component count in the original graph.

For each fixed retained size jj and component count cc, the exceptional-set sum is

cj,k,c=∑h≤kNj,h,c(j−hk−h).(45)c_{j,k,c}=\sum_{h\le k}N_{j,h,c}\binom{j-h}{k-h}. \tag*{(45)}

We apply (29) separately for every cc and sum over hh. The component-count array has polynomially many entries, and its nonnegative counts have polynomial bit length. The outer exponents are those of Theorem 1. For a prescribed pair of statistics, prefix-pin counts give unranking exactly as before, using O(n)O(n) full-count calls.

Sparse companion constructions

Hamilton cycles and the full forest polynomial

For an arc u→vu \to v, make two optional terms on the physical atoms outu,inv\mathrm{out}_u,\mathrm{in}_v. The grade-zero term has weight one. The grade-one term has weight minus the sign needed to put out⁡uin⁡v\operatorname{out}_{u}\operatorname{in}_{v} into canonical atom order. At every vertex require equal incoming and outgoing grades, and at a fixed root require grade zero. Every surviving cover is a directed cycle cover with constant grade on each cycle. If AA is the active vertex set, the exterior sign is sgn⁡(πA)\operatorname{sgn}(\pi_A) and the explicit signs supply (−1)∣A∣(-1)^{|A|}. Thus each active cycle has weight −1-1, and a cover with cc cycles contributes (1−1)c−1(1-1)^{c-1}. The complete signed sum is exactly the integer Hamilton count.

For forests, use the 2n2n Grassmann atoms ψˉ1,ψ1,…,ψˉn,ψn\bar{\psi}_1,\psi_1,\ldots,\bar{\psi}_n,\psi_n, set τv=ψˉvψv\tau_v=\bar{\psi}_v\psi_v, and let Top extract the coefficient of τ1⋯τn\tau_1\cdots\tau_n in canonical order. The imported forest identity is

Top⁡∏v(1+τv)∏uv∈E(1+UQuv)=∑F forestU∣F∣(46)\operatorname{Top}\prod_v(1+\tau_v)\prod_{uv\in E}(1+UQ_{uv})=\sum_{F\ \mathrm{forest}}U^{|F|} \tag*{(46)}

where Quv=(ψˉu−ψˉv)(ψu−ψv)−τuτvQ_{uv}=(\bar{\psi}_u-\bar{\psi}_v)(\psi_u-\psi_v)-\tau_u\tau_v. We replace each edge factor by the product of its five elementary monomial factors, and each vertex factor by its single mass factor. This is an integer identity: the even monomials commute, each has square zero, and all products of two distinct summands within QuvQ_{uv} cancel, since its quadratic part is decomposable and its quartic part overlaps it. Equivalently, the product is the finite exponential of UQuvUQ_{uv}, which equals 1+UQuv1+UQ_{uv}. Each elementary term has two or four physical atoms and grade one. There are O(n+m)O(n+m) ports, so (5) applies. The degree in UU of each selected-term contribution is at most nn; cancellation gives the usual forest degree at most n−1n-1. Coefficient recovery uses Appendix A. Both the Hamilton count and every coefficient of the forest polynomial are bounded by

∑j=0n(mj)≤(m+nn)≤[e(1+m/n)]n.(47)\sum_{j=0}^{n}\binom{m}{j}\le\binom{m+n}{n}\le[e(1+m/n)]^n. \tag*{(47)}

For Hamilton cycles the simpler product-of-outdegrees bound also works. An additional factor 2n2^n covers all vertex selections below. Thus p=O(s)p=O(s) suffices, and the O(n)O(n) extra interpolation bits preserve P=O(s)P=O(s).

Hamilton and forest counts. Under Hypothesis 1, directed Hamilton cycles and all edge-cardinality counts of unrooted spanning forests in an nn-vertex, mm-edge graph can be computed deterministically in

poly⁡(n+m) 2O(s/log⁡(s+2))(48)\operatorname{poly}(n+m)\,2^{O\left(s/\sqrt{\log(s+2)}\right)} \tag*{(48)}

time and polynomial space, with ss as in (3). The bound includes integer recovery and Hamilton witness recovery. Undirected Hamilton cycles on at least three vertices follow by bidirecting the edges and dividing the integer answer by two.

Proof. The scalar network satisfies the contraction premise at the claimed scale. For sufficiently large nn, the maximum degree in the preceding lemma is at most ⌈s9/10⌉\lceil s^{9/10}\rceil. The number of vertices and the description length are polynomial, and local entries take polynomial time and space. We use Hypothesis 1 with ℓ=1\ell=1 and the precision just proved. The array exponent O(nlog⁡n)O(\sqrt{n}\log n) and the polynomial number of interpolation calls are absorbed by (48). We enumerate arrays and calls sequentially. Bounded exceptional sizes use direct enumeration. Hamilton recovery deletes an arc whenever the remaining count is nonzero, yielding a single cycle in at most mm further calls. All subgraphs retain the original budget as an upper bound. □\square

In particular, (48) is vertex-subexponential when log⁡(1+m/n)=o(log⁡n)\log(1+m/n)=o(\sqrt{\log n}). For m/n≤(log⁡n)Cm/n\le(\log n)^C, fixed CC, it is 2O(nlog⁡log⁡n/log⁡n)poly⁡(n+m)2^{O(n\log\log n/\sqrt{\log n})}\operatorname{poly}(n+m). For m=O(n)m=O(n) it retains 2O(n/log⁡n)2^{O(n/\sqrt{\log n})}. The dense worst case m=Θ(n2)m=\Theta(n^2) still has s=Θ(nlog⁡n)s=\Theta(n\log n); the scale is Θ(nlog⁡n)\Theta(n\log n).

Steiner counting, high-degree selectors, and original witnesses

Let a nonempty terminal set TT be fixed. Introduce selector bits zvz_v, pin zv=1z_v=1 for v∈Tv\in T, give each selected vertex weight VV and each unselected vertex weight UU, and replace an edge weight in (46) by UzuzvUz_uz_v. The exact polynomial is

B(U,V)=∑S⊇TUn−∣S∣V∣S∣∑F⊆E(S), F forestU∣F∣.(49)B(U,V)=\sum_{S\supseteq T}U^{n-|S|}V^{|S|}\sum_{\substack{F\subseteq E(S),\ F\ \mathrm{forest}}}U^{|F|}. \tag*{(49)}

Its coefficient [Un−1Vj][U^{n-1}V^j] counts precisely the jj-vertex Steiner trees as pairs (S,F)(S,F), each once.

Each selected elementary edge term now has two positive predicate ports, requiring zu=zv=1z_u=z_v=1, in addition to its physical atoms. A classical column tensor contributes VV for a vertex touched by such a port and U+VU+V for an untouched unpinned vertex. Fixed selector weights are scalars. At most nn elementary terms can be selected, so the total number of selected physical and classical ports is at most 4n4n. The entropy bound (5) and the row-load bound survive. Classical columns require a separate degree argument.

First consider m≤n17/16m\le n^{17/16}. We pin every unpinned selector whose original graph degree exceeds n3/4n^{3/4}, in all possible ways. There are at most 2m/n3/4=O(n5/16)2m/n^{3/4}=O(n^{5/16}) such vertices, and these branches partition the selected sets. We remove terms that require a pinned zero and remove predicates already fixed to one. Each remaining classical vertex has O(n3/4)O(n^{3/4}) input incidences. Greedily balancing their incidence weights among JJ columns gives raw load

O((n+m)/J+n3/4)=O(n13/16)(50)O((n+m)/J+n^{3/4})=O(n^{13/16}) \tag*{(50)}

per column. Subset-index wire degree never exceeds raw incidence count. Thus all classical columns satisfy the source degree condition as well.

The polynomial in (49) has separate degrees at most 2n2n and nn even before cancellation. We use (34) with p+3np+3n bits at the scalar grid; (47) with the extra 2n2^n factor bounds every final coefficient. The high-degree branches cost 2O(n5/16)2^{O(n^{5/16})}, absorbed by (48). For m>n17/16m>n^{17/16}, enumerate vertex subsets and compute the spanning-tree count of each induced subgraph by a Laplacian cofactor. This costs 2npoly⁡(n+m)2^n \operatorname{poly}(n + m) time and polynomial space, already within (48) because s=Ω(nlog⁡n)s = \Omega(n \log n) in this density range. This fallback ensures the following statement applies to every simple graph.

Steiner edge-tree counts. All vertex-cardinality Steiner tree counts, the minimum cardinality, and a minimum tree witness satisfy (48), deterministically in polynomial space under Hypothesis 1. The same bound holds with additional selector pins, forbidden edges, and at most n−1n - 1 required forest edges.

Proof. The preceding construction proves counting. A required edge contributes the factor UQuvUQ_{uv}, whose five alternatives form one required factor, handled by the additional balanced rows. More than n−1n - 1 required edges, or a required cycle, gives zero. For dense fallback, required acyclic edges can be contracted before applying the cofactor formula to each selected graph, with parallel-edge multiplicities retained.

We choose the smallest nonzero cardinality coefficient. We pin original vertices one at a time while retaining a nonzero coefficient. Once the selected set is fixed, delete edges while retaining a nonzero count. The final edge-minimal connected graph is a tree. This uses at most O(n+m)O(n + m) complete count queries and returns original vertices and edges. Unranking and sampling can similarly use original selector and edge inclusion/exclusion queries. □\square

Finite checks. The algebraic and reduction layers were checked on every nonisomorphic simple graph with at most ten vertices.

References

  1. [1]Bodlaender, H.L., Cygan, M., Kratsch, S., Nederlof, J.: Deterministic Single Exponential Time Algorithms for Connectivity Problems Parameterized by Treewidth (2015). https://doi.org/10.1016/j.ic.2014.12.008, Information and Computation 243, 86–111
  2. [2]Caracciolo, S., Jacobsen, J.L., Saleur, H., Sokal, A.D., Sportiello, A.: Fermionic Field Theory for Trees and Forests (2004), https://arxiv.org/abs/cond-mat/0403271, Physical Review Letters 93, 080601
  3. [3]Claude (Anthropic): A 2⁽ⁿ⁾ Time Algorithm for 3-SAT (2026), https://github.com/anthropics/formal-math/blob/main/eth/paper.pdf, 26 October 2026
  4. [4]Cygan, M., Nederlof, J., Pilipczuk, M., Pilipczuk, M., van Rooij, J.M.M., Wojtaszczyk, J.O.: Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time (2011), https://arxiv.org/abs/1103.0534, FOCS; journal version, ACM Transactions on Algorithms 18(2), 2022
  5. [5]Li, J., Nederlof, J.: Detecting Feedback Vertex Sets of Size k in O*(2.7ᵏ) Time (2020), https://arxiv.org/abs/1906.12298, SODA
  6. [6]Naor, J., Naor, M.: Small-Bias Probability Spaces: Efficient Constructions and Applications (1993). https://doi.org/10.1137/0222053, SIAM Journal on Computing 22(4), 838–856
  7. [7]Novotná, J., Okra, K., Pilipczuk, M., Rzążewski, P., van Leeuwen, E.J., Walczak, B.: Subexponential-Time Algorithms for Finding Large Induced Sparse Subgraphs (2019), https://arxiv.org/abs/1910.01082, IPEC, LIPIcs 148, Article 23
  8. [8]OpenAI: The Exponential Time Hypothesis is False. OpenAI Math Release preprint (2026), https://github.com/openai/math/blob/main/preprints/The-Exponential-Time-Hypothesis-is-False-October-25-2026/paper.pdf, 25 October 2026
  9. [9]Raghavan, P.: Probabilistic Construction of Deterministic Algorithms: Approximating Packing Integer Programs (1988). https://doi.org/10.1016/0022-0000(88)90003-7, Journal of Computer and System Sciences 37(2), 130–143
  10. [10]Staples, G.S.: Hamiltonian Cycle Enumeration via Fermion Zero-Dimensional Convolution (2017). https://doi.org/10.1007/s10773-017-3381-z, https://arxiv.org/abs/1408.1036, International Journal of Theoretical Physics 56, 3923–3934

Paper details

vlnc:W_zpjrke7c
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents