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 -vertex, -edge simple graph, we compute the complete size distribution deterministically in 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 be a simple undirected graph with vertices and 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 -vertex graph admits deterministic computation of all feedback vertex set cardinality counts in
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.

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 . 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 . The outer algorithm guesses a set containing them. Outside , a retained vertex has at most 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 . The process ends with a graph of bounded density, where the compressed counter applies with degree caps. Choosing of order and the branching threshold of order keeps both the exceptional-set guesses and the leaf count within the final exponent.
Binomial inversion removes overlap between guesses. The branches for one are disjoint, but a forest can admit several exceptional-set guesses. A size- forest with genuinely high-degree retained vertices occurs in exactly guesses of size . Summing the leaf counts by therefore gives a triangular binomial transform of the desired 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 and Steiner trees in . Their structural parameter is treewidth. The FVS comparisons in Table 1 distinguish decision, optimization, and complete counting.
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 . 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 for which 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 and let a bipartite Boolean tensor network have wires, polynomially many vertices, maximum degree at most , and description length . Its entries lie in , with . Suppose a local entry is computable in time and polynomial space. Then its contraction is computable deterministically in time and polynomial space.
Theorem 2 (Sparse parity checks, from [8 Lemma 6.1]). For positive integers , , put , , , and . There is a binary matrix with columns, at most rows of support at most , and no nonzero kernel word of weight less than .
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 Grassmann atoms , set , and let extract the coefficient of in canonical order. The imported forest identity is
where . 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 cancel, since its quadratic part is decomposable and its quartic part overlaps it. Equivalently, the product is the finite exponential of , which equals . Each elementary term has two or four physical atoms and grade one. There are ports. The degree in of each selected-term contribution is at most ; cancellation gives the usual forest degree at most .
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.
Choose the thresholds , of § 6 and enumerate exceptional retained sets of size at most from (24).
For each , branch on high-current-degree vertices outside , specifying the exact retained neighbours in a retaining branch. The disjoint-leaf lemma in § 6 bounds the number and density of the leaves.
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.
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 physical wires. We encode selected ports and factor the signs into ordinary scalar tensors. We put
All graphs in this section are simple, so .
An ordinary network for signed covers of atoms
We use 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 . 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 consecutive groups, each of size at most . 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 , an atom group , and a grade . Let be the number of possible ports in that bucket. We enumerate their selected counts . Only physical ports are selected, and each atom column has its prescribed total size. For a fixed count array, use
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 , 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
:::`
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 . Suppose the input has ports, selected ports, and selected terms of bounded support. The signed cover sum is a sum of ordinary networks, each with wires, maximum degree , 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 buckets. With selected ports, source Appendix D.3’s product bound gives
The arrays have at most possibilities. Every selected optional term consumes its owner atom, so a factor group can contain only 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 selected ports as well. Therefore the wire degree of either vertex is at most , 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 required factors, each a sum of a fixed number of even monomials. We put these factors in additional rows, balancing their number. A row checks that exactly one alternative is selected per required factor. Its selected load is again ; 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 be the number of vertices pinned deleted and the number of unpinned vertices. Every choice of the free vertices induces a forest, so the deletion-size generating polynomial is
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 be a simple graph with vertices and edges. We set
In particular and . We consider the finite object set
We write and . Its violation coordinate is (mod 2) for . Thus exactly when . Every induced forest has exactly one zero-violation object. Also
The second inequality follows by the Vandermonde convolution with . All counts refer to the objects in (7).
The parity filter and object-mass bound
For a binary matrix with columns, let
Every coefficient is nonnegative and . We apply Theorem 2 with the object-mass parameter and
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 , , and . If use no local checks. Otherwise let , choose distinct , and impose
We expand each field equation into binary equations. Any at most 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 . The binary row count satisfies because .
A field presentation can be found by enumerating irreducible binary polynomials of degree ; even trial factoring costs polynomial time in . Local-code construction is therefore polynomial in .
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
Lemma 5 (Exact separation). Let be the object polynomial in (9), with , as in (6) and (10), and with the initial sparse-check matrix of Theorem 2. At most additional parity rows, each of support at most , suffice to obtain
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 , with uniform edge coordinates and independent coefficient bits, hits the support of each surviving nonzero violation with probability greater than . Conditional on a hit, its row parity is uniform. It therefore rejects each such object with probability at least . If is their surviving number, a minimum-count row leaves at most . The zero-violation count is independent of the row. After rows the remaining number is less than , hence zero. Elimination is objectwise and therefore holds for every restricted subfamily and every coefficient. Appendix § 12 constructs these rows using at most weighted queries, where .
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 , . We give each edge factor the six states: empty, or one of the five canonical monomials of . 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 .
For a fixed edge set , the signed sum of these choices and of vertex mass choices is the coefficient of in the multivariate identity. It is one when is acyclic and zero otherwise. This follows coefficientwise, since the original identity allows independent formal weights . Multiplication by any function of and the edge-event vector preserves the coefficientwise cancellation. In particular it permits the parity indicators defining (9), arbitrary pins of or , and the deletion weight.
Integral parity lift and its total order budget
A row of gives a parity of terms and . Its support has size at most or , so it has at most
monomials, each of degree at most two. After any pins, remove zero terms, move constants to the right side, and cancel duplicate terms over . The surviving row has the form , where every is a positive predicate , , or . Its integer indicator is
The empty selection has coefficient ; a nonempty selection of distinct terms has coefficient . These are integer coefficients; there is no division by two inside .
Let be the number of parity rows. A product selection of total order has valuation at least . Therefore retain only
All other terms vanish coefficientwise modulo , before any Grassmann cancellation or summation over selectors. For a parity predicate , an edge column requires the whole-edge event to be selected. For or , 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 groups. There are graph-factor rows, parity-factor rows, physical-atom columns, vertex-selector columns, and edge-event columns.
Assign every selected graph monomial to the group containing its smallest physical atom. We partition the parity rows into groups with at most 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 and additionally the total parity order in each parity group, requiring their sum at most . 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 if it is unpinned and unrequired. A pinned deleted vertex contributes . 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 in the ring
There are exactly selected physical ports, at most graph selector ports, at most edge-event ports, and at most parity predicate ports. We put . The input has ports. The subset entropy bound gives
There are at most public arrays, including the order counters. They can be streamed in polynomial space.
For the degree argument first suppose . In the unrestricted oracle network, pin every or with more than input incidences, in all ways. There are such variables. Each branch restricts the objects in (7), so the branches sum without multiplicity. A pinned requires the macro event, and its parity occurrences disappear upon normalization; a pinned deletes its macro alternatives. An inconsistent edge and vertex pin gives zero. After normalization, the remaining unpinned variables have incidence at most . 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 : each selected graph monomial consumes its owner atom. Its wire degree is at most . The same bound holds for physical columns. Each parity row group has raw load ; each balanced classical column has raw load . For any bucket, , so raw load bounds wire degree where needed. Using , , gives
These loose polynomial logarithmic factors suffice: . For sufficiently large 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 -vertex, -edge graph can be computed deterministically in polynomial space and time
The same bound includes a minimum deletion set and unranking any deletion set of specified cardinality. Direct 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 . For , (18) is bounded by a constant times
since . We choose an integer scale that is a sufficiently large constant multiple of (21). The network has wires, maximum degree at most , polynomial-size descriptions and polynomial-time local entries. The coefficient precision and truncation length are both . Hypothesis 1 applies to (17). For these unweighted calls, arrays and pin branches are enumerated sequentially. Their exponents, and , are absorbed in . 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 is less than 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 , then and the exponent in (20) dominates for sufficiently large . 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 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 be a graph on vertices with a set pinned retained. We require for every retained . In the intermediate object set (7), impose instead
After separation , 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 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 , with 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 graph-event occurrences remain at a capped vertex; its parity occurrences disappear upon normalization. Thus the classical column load bound becomes
For leaf size comparable to the original size up to a logarithmic factor, 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 and set
Every forest induced on has at most vertices of degree greater than , since its degree sum is at most . Denote this set by . We enumerate all sets of size at most . For fixed , the subproblem counts
with any additional original selector pins. If has a cycle or a vertex of is pinned deleted, this count is zero.
Maintain an active induced graph and a set of vertices pinned retained, initially including and the original retained pins. Deleted pins are removed from . If there is of current degree , proceed as follows. If , create one branch deleting . For every possible exact selected-neighbor set
create a branch retaining , pinning every vertex of retained, and deleting every vertex of . If (26) has no solution, there is no retaining branch. We use a deterministic rule to choose .
Lemma 7 (Disjoint leaves and their density). Fix integers and an exceptional retained set 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 has input degree at most and the number of edges is at most , where . Its solutions are exactly the pinned induced forests with degree cap on . The number of leaves is at most
The leaves can be streamed with polynomial working space.
Proof. A solution either omits or retains it. In the latter case, is its unique valid set in (26), because has degree at most in the final induced graph. Pinning both and 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 active vertices; none is already pinned retained by (26). There can be at most such steps on a path, while every path has at most steps in total. Each retaining step has at most 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 are at most in the whole active graph, including neighbors in . Edges with an endpoint outside number at most . Edges entirely in number at most when is nonempty, since was checked acyclic. For the simpler bound applies. Both imply . The cap in (22) enforces every remaining condition of (25). □
Removing multiplicities between exceptional sets
Different can still represent the same induced forest. Let be the number of original induced forests with retained vertices and exactly vertices of degree greater than . For , sum the leaf counts for all -element , and let be their number of -vertex solutions. For a fixed solution with and , its admissible guesses are exactly the sets of size . Therefore
Terms with impossible sizes are zero. For each , recover in order
The total number of induced forests of size is , since every such forest has . The triangular matrix in (28) has diagonal one, so no division or precision loss occurs. Moreover ; all reconstruction and accumulation use polynomially many bits. Original selector pins preserve (28), because for each surviving all of its admissible are still enumerated.
Proof of Theorem 1. The proof combines the sparse leaf cost with the exceptional-set and branch counts. Let , choose max and . For sufficiently large , (24) gives . The number of exceptional guesses is bounded by
For each guess, (27) gives leaves; the additive is absorbed for sufficiently large . Neither bound assumes the input sparse.
If a leaf has vertices, enumerate its subsets and check forest membership, pins, and degree caps directly. This costs . Otherwise , and the density bound gives . The capped extension (23) applies: , so the residual event load at every pinned capped vertex is below for sufficiently large . 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
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 sequentially, using the original retained size 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 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 while using for deletions. At a vertex use mass and at an edge use . Deleted isolated vertices then have mass one. The separated polynomial is
For an -vertex leaf, evaluating at 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
can be computed deterministically in polynomial space and time
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 in (32); a single retained vertex is a tree, while the empty set has 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 and . Its leaf cost and branch bound are within (33), and every remaining input vertex has degree at most . The capped marked counter with 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 .
Corollary 10. Assuming Hypothesis 1, these three counting problems admit deterministic algorithms in 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 and , the time is .
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 have integer coefficients and degree at most . Values at modulo determine all its power coefficients modulo . Indeed,
and is divisible by for an integer-coefficient polynomial. Removing , then inverting the odd part of modulo , is valid because .
For separate degrees , apply this procedure successively using precision at the evaluation grid. Only polynomially many scalar contractions are used.
Constructing the sparse-check shifts
Lemma 11 (Polynomial-time shift construction). Let , be an integer, , and . A deterministic algorithm constructs such that, for every nonzero ,
Its bit complexity and space are polynomial in . For the parameters of source Lemma 6.1, this replaces the exhaustive shift search by polynomial time in 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 , , and . After choices let and
For uniform next shift , each nonzero character is balanced. Therefore the average next potential is . Choosing a shift that minimizes it gives . For ,
Here logarithms are natural. Moreover and . Consequently . If any , its term alone is at least , a contradiction.
No real arithmetic or approximate comparison is needed. At step store the two integers
Their exponents of and are , hence nonnegative. Initially both are one. We write , . A positive character multiplies by , and a negative character by . Minimizing the next potential is equivalent to minimizing
All scores are the Walsh transform of the difference vector, with zero at character zero. A fast exact transform uses integer additions per chosen shift. The stored integers have bits; there are of them, and updates multiply by integers of bits. All operations have polynomial bit complexity and space, including the output list.
At the source interface set , , and take the least power of two with . If , every shift is zero and there is no nonzero character to constrain. Otherwise , , and . Thus all assumptions hold. In this nontrivial case and is polynomial in , so the construction is polynomial in . Its bias is stronger than the source’s required . 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 . Every nonzero violation surviving the initial matrix has weight at least . For this is the source distance bound; for it follows from its integer weight being at least one. Thus a random length- list still rejects every such violation with probability at least .
For current rows , prefix row , and , define the nonnegative integer moment
The pinned and degree-capped object family is permitted, and . The weight counts ordered -tuples of coordinates at which , giving a direct nonnegative counting interpretation. If random list positions remain, the expected number accepted by the final appended row is exactly
Indeed a random position has character expectation , and the positions are independent. Expanding the indicator proves (36).
At the next position enumerate only its choices. For each compute 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 positions yields a row at least as good as the initial random-list expectation. Repeating at most times gives exact separation by the same argument as before. There are at most weighted oracle calls, plus an initial unweighted count if early stopping is used. The last-position moment has and is already the unweighted count of the chosen row.
Lemma 12 (Weighted ordinary-network oracle). For and sufficiently large , put . Every weighted moment or in (35), for and for the pinned, degree-capped object family specified there, has an ordinary scalar-network representation with the same asymptotic root scale as (21). Its complete evaluation cost under D.1, including public arrays and heavy-variable pins, is 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, . The integer violation weight is therefore . We add the factor
It is a function only of selectors and whole-edge events, so it preserves the coefficientwise forest cancellation. On genuine objects it equals . The prefix row 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 and its support bounds remain and .
We represent (37) by labeled slots. Each slot chooses the constant , one term , or one term . 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 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
Every required nonnegative count is less than . Thus the least nonnegative residue is the exact integer used in the comparison. The parity-lift order cutoff must be recomputed as , where is the current row count. For the stated density range, , hence and . There are only additional selected ports. The original selected-port and precision budgets are preserved.
Raw incidence is now
The subset entropy bound still gives wires, since . With the same groups, the additional row has wire degree by its selected-port bound. We pin variables of incidence greater than and rebalance the classical columns as before. The number of pinned variables and the maximum remaining degree are bounded respectively by
For capped FVS leaves, add the same residual event load from (23); is polylogarithmic and is absorbed. Since , the degree condition of Theorem D.1 holds for sufficiently large . The extra factor row adds buckets, so the array exponent is . Both this exponent and the pin-branch exponent in (38) are absorbed by . 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 , 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 for the component marker and for the deletion marker. For a fixed selector vector with retained set , put
The multivariate identity is
Indeed, after fixing , deleted vertices have no incident edge terms and their mass integral is one. On , source equation (13) has uniform parameters , , hence one factor per forest component. Thus (40) follows over the integers coefficientwise in the independent edge variables. It also holds for , whose component exponent is zero.
We keep the whole-edge macro convention of Section 5. We multiply each quartic edge monomial’s coefficient by . For a mass term at a pinned retained vertex, multiply its coefficient by ; 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 record whether that mass term was selected. An unpinned vertex required retained by an edge macro or parity predicate contributes at its column. If it has no such requirement, its column sums the two choices with factor
Pinned deleted vertices contribute 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 additional selected mass-event ports on an -vertex leaf. The total selected-port bound becomes , and input incidence increases by at most . 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 , the resulting polynomial is exactly
where includes the current pins and degree caps. The greedy separation of Lemma 5 is applied at , . Its completed matrix rejects every incorrect object, independently of . Hence its final polynomial is
The same separating matrix serves every component value.
Two statistics with one formal variable
The degree in is at most even before cancellation in the signed-cover expansion. Every selected mass contributes at most one and consumes two physical atoms; every quartic edge contributes one and consumes four. There are only atoms. The deletion degree is also at most .
Let , with defined for the leaf as in (6). For each integer , contract the marked network at over
The lifted parity truncation uses this increased precision, so its total retained order is . Both the precision and the one formal truncation length remain at the source root scale. Local entries compute powers of modulo , using bits of precision.
For each deletion coefficient , apply the integer-polynomial Newton recovery (34) to . Its degree is at most , and the th difference is divisible by . Removing the power of two in loses at most bits, and the odd factor is invertible. Thus the values modulo determine every power coefficient modulo . All final coefficients count vertex sets and are at most , so their least nonnegative residues are the exact integers.
Only 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 and its component count is exactly the component count in the original graph.
For each fixed retained size and component count , the exceptional-set sum is
We apply (29) separately for every and sum over . 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 full-count calls.
Sparse companion constructions
Hamilton cycles and the full forest polynomial
For an arc , make two optional terms on the physical atoms . The grade-zero term has weight one. The grade-one term has weight minus the sign needed to put 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 is the active vertex set, the exterior sign is and the explicit signs supply . Thus each active cycle has weight , and a cover with cycles contributes . The complete signed sum is exactly the integer Hamilton count.
For forests, use the Grassmann atoms , set , and let Top extract the coefficient of in canonical order. The imported forest identity is
where . 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 cancel, since its quadratic part is decomposable and its quartic part overlaps it. Equivalently, the product is the finite exponential of , which equals . Each elementary term has two or four physical atoms and grade one. There are ports, so (5) applies. The degree in of each selected-term contribution is at most ; cancellation gives the usual forest degree at most . Coefficient recovery uses Appendix A. Both the Hamilton count and every coefficient of the forest polynomial are bounded by
For Hamilton cycles the simpler product-of-outdegrees bound also works. An additional factor covers all vertex selections below. Thus suffices, and the extra interpolation bits preserve .
Hamilton and forest counts. Under Hypothesis 1, directed Hamilton cycles and all edge-cardinality counts of unrooted spanning forests in an -vertex, -edge graph can be computed deterministically in
time and polynomial space, with 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 , the maximum degree in the preceding lemma is at most . The number of vertices and the description length are polynomial, and local entries take polynomial time and space. We use Hypothesis 1 with and the precision just proved. The array exponent 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 further calls. All subgraphs retain the original budget as an upper bound.
In particular, (48) is vertex-subexponential when . For , fixed , it is . For it retains . The dense worst case still has ; the scale is .
Steiner counting, high-degree selectors, and original witnesses
Let a nonempty terminal set be fixed. Introduce selector bits , pin for , give each selected vertex weight and each unselected vertex weight , and replace an edge weight in (46) by . The exact polynomial is
Its coefficient counts precisely the -vertex Steiner trees as pairs , each once.
Each selected elementary edge term now has two positive predicate ports, requiring , in addition to its physical atoms. A classical column tensor contributes for a vertex touched by such a port and for an untouched unpinned vertex. Fixed selector weights are scalars. At most elementary terms can be selected, so the total number of selected physical and classical ports is at most . The entropy bound (5) and the row-load bound survive. Classical columns require a separate degree argument.
First consider . We pin every unpinned selector whose original graph degree exceeds , in all possible ways. There are at most 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 input incidences. Greedily balancing their incidence weights among columns gives raw load
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 and even before cancellation. We use (34) with bits at the scalar grid; (47) with the extra factor bounds every final coefficient. The high-degree branches cost , absorbed by (48). For , enumerate vertex subsets and compute the spanning-tree count of each induced subgraph by a Laplacian cofactor. This costs time and polynomial space, already within (48) because 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 required forest edges.
Proof. The preceding construction proves counting. A required edge contributes the factor , whose five alternatives form one required factor, handled by the additional balanced rows. More than 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 complete count queries and returns original vertices and edges. Unranking and sampling can similarly use original selector and edge inclusion/exclusion queries.
Finite checks. The algebraic and reduction layers were checked on every nonisomorphic simple graph with at most ten vertices.
References
- [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]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]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]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]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]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]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]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]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]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