CS Paper Radar

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

Mengyang Wu, Minghao Wang

cs.DS ·submitted 2026-11-02 05:20 UTC · v1
theoryhot direction

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 $n$-vertex, $m$-edge simple graph, we compute the complete size distribution deterministically in $\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.

Comment
27 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Single-Exponential Algorithms for Directed Feedback Vertex Set on Planar Digraphs

cs.DS ·2026-09-26 ·Daniel Lokshtanov, Saket Saurabh, Jie Xue
theory similarity 0.65
Abstract

We consider Directed Feedback Vertex Set on planar digraphs, parameterized by the solution size $k$. We give a randomized algorithm with one-sided error running in time $(2+\sqrt5)^k n^{O(1)}= 4.24^k n^{O(1)}$, and a deterministic algorithm running in time $8.04^k n^{O(1)}$. Both algorithms use polynomial space. To the best of our knowledge, these are the first single-exponential fixed-parameter algorithms for Directed Feedback Vertex Set on planar digraphs. This contrasts with general digraphs, where the best known algorithms run in time $2^{O(k\log k)}(n+m)$, and whether a $2^{o(k\log k)}n^{O(1)}$-time algorithm exists remains a major open problem. Our main tool is an exact Euler-type counting identity for plane digraphs. It shows that every small solution must carry a large share of the vertices whose in- and out-arcs alternate in the embedding, while solutions avoiding such vertices can be computed by reducing to Directed Feedback Arc Set, which is known to be solvable in polynomial time on planar digraphs via the Lucchesi-Younger theorem.

0.38

Approximating #BIS in $\exp(\widetilde O(n^{1/3}))$ Time

cs.DS ·2026-11-04 ·Jingcheng Liu, Yitong Yin
similarity 0.65
Abstract

We give randomized algorithms for approximately counting and nearly uniformly sampling independent sets in arbitrary bipartite graphs (#BIS). At fixed accuracy, both algorithms run in $\exp(O(n^{1/3}\log^{4/3}n))$ time on $n$-vertex graphs. More generally, the same running-time dependence on the number of variables holds for approximate counting and sampling with efficiently evaluable positive log-supermodular weights on Boolean variables. A weighted Sinclair-Jerrum walk on the self-reduction tree reduces these tasks to coarse lower estimates of residual log-partition functions. We obtain these estimates by optimizing a concave relaxation of an exact variational principle on the tree; threshold smoothing certifies that the low-degree search suffices.

0.29

Faster Algorithms for Finding Small Induced Patterns in Sparse Host Graphs

cs.DS ·2026-09-30 ·Priyanshi Agrawal, Balagopal Komarath
similarity 0.64
Abstract · 38 pages, 70 figures

We study algorithms for detecting induced subgraphs corresponding to fixed pattern graphs in host graphs. We show that at least five of the 21 connected graphs on five vertices can be detected in time roughly the product of the number of vertices and the number of edges, and that at least 65 of the 112 connected graphs on six vertices can be detected in time nearly quadratic in the number of edges. We also give algorithms for detecting induced paths and cycles on seven vertices, running in time roughly the number of vertices times the square of the number of edges. Our main technical tool is a generalized notion of tree decomposition width, called (p, q)-width. It yields algorithms whose running times depend on both the number of vertices and the number of edges, and are never worse than existing bounds. Whenever the host graph has fewer than roughly quadratically many edges in its number of vertices, our bounds are strictly faster. For some patterns, including the seven-vertex cycle, our algorithms are optimal under standard complexity-theoretic assumptions. We further develop this approach using pattern-based polynomials that exploit the structure of tree decompositions, not just their width. This gives algorithms for detecting induced paths and cycles on an even number of vertices in bipartite graphs, running in time roughly the (k-1)-th power of the number of edges for paths on 2k vertices, and that same bound times the number of vertices for cycles on 2k vertices. These are faster than the best known algorithms for general graphs.

0.16

Output-linear time enumeration of potential maximal cliques

cs.DS ·2026-10-14 ·Pierre Bergé, Vincent Limouzy, Nicolas Schivre
top venue similarity 0.64
Abstract · This paper was accepted at SODA 2027. 54 pages, 18 figures

First defined by Bouchitté and Todinca, Potential Maximal Cliques (PMC) are a well studied notion in graph theory due to its numerous applications. The PMCs of an undirected graph $G$ are defined as the maximal cliques of the minimal triangulations of $G$. Their number can be exponential in the size of the graph. PMCs were crucial in the design of a polynomial-time algorithm which solves Maximum Weight Independent Set on $P_6$-free graphs (Grzesik, Klimošová, Pilipczuk, Pilipczuk, 2020). They also play a central role in the proposal of a polynomial-time algorithm to solve Largest Induced Subgraph of treewidth $\le t$ (Fomin, Todinca, Villanger, 2013). Last but not least, certainly one of the main application of PMCs is the existence of an exact dynamic-programming algorithm to determine the treewidth of a graph (Fomin, Kratsch, Todinca, Villanger, 2008) which uses its list of PMCs as an input. In fact, the enumeration of PMCs stands as the bottleneck for the computation of treewidth with this method: the PMC-enumeration step takes output-quadratic time (Bouchitté, Todinca, 2002) while the dynamic-programming one takes a time linear in the number of PMCs. This two-step procedure was proven to be among the most performing approaches in practice to determine treewidth. Answering a longstanding open question, we propose an algorithm to enumerate PMCs in output-linear time, i.e. a running time linear in the number of PMCs. This offers nice perspectives not only from the theoretical viewpoint - better running time for the PMC-based methods determining treewidth, for Minimum Fill-In and Largest Induced Subgraph of treewidth $\le t$ - but also from the practical side, with the possibility to propose top-performance implementation.

0.68

Subexponential-Time Exact-One Hitting Set

cs.DS ·2026-10-31 ·Shiteng Chen, Tao Jiang, Yijie Zhu
theory similarity 0.64
Abstract · 33 pages, full version including proofs and appendices

Exact-One Hitting Set is one of Karp's original 21 NP-complete problems: given an explicitly listed family of subsets of an $r$-element ground set, decide whether a subset meets every input set in exactly one element. Combining our reduction with the fixed-width exact-counting theorem of OpenAI (2026), we obtain a deterministic polynomial-space algorithm that computes the exact number of feasible selections in time $2^{O(r\log\log(r+16)/\sqrt{\log(r+16)})}\operatorname{poly}(L+1)=2^{o(r)}\operatorname{poly}(L+1)$, where $L$ is the input length. The number and widths of the input sets are unrestricted. Known row selection retains at most $r+1$ input constraints, but their total width may remain quadratic. Our path representation of two-query counting cancellation constructs two ordinary 3-CNF formulas with at most $2r$ variables and $O(r^2)$ clauses each, whose model counts differ by the desired answer. The auxiliary-variable budget depends on the number of simultaneous conditions, not on their widths or on the numbers of witnesses. We extend this construction to signed equations with fixed bounded demands and positive integer coefficients. We also represent every explicitly listed Boolean relation of VC dimension at most one by binary clauses and signed exact-one equations on its original variables, obtaining the same two-query variable bound for unrestricted overlaps among such local constraints. A bounded-term version further handles fixed finite/cofinite local degree rules on arbitrary graphs. The path representation is related by variable elimination to existing marker--parity cancellation.

0.27

Quasi-polynomial-sized vertex multicut-mimicking networks and kernelization for Vertex Multiway Cut

cs.DS ·2026-11-05 ·Eduard Eiben, Roohani Sharma, Magnus Wahlström
survey similarity 0.63
Abstract

We give deterministic polynomial-time constructions of vertex multicut-mimicking networks of quasi-polynomial size. Given a graph G, a terminal set T, and a positive integer c, our algorithm constructs a graph with |T|^7 c^{O( log c ) } vertices that preserves every minimum vertex multiway cut value of at most c, for every partition of the terminals. Setting c=|T| gives an exact vertex multicut-mimicking network with |T|^{O( log |T| ) } vertices, resolving an open question of Wahlström [ACM Transactions on Algorithms 2022], who showed a bound of κ^{O( log^3 κ)} for the edge multicut-mimicking variant, where κ:= \sum_{t \in T} |N_G(t)| is the capacity of the terminal set, which was later improved to κ^{O( log^2 κ)} by Anand, Lee, Li and Saranurak [STOC 2024]. As applications of our vertex multicut-mimicking network, we obtain deterministic kernels of size k^{O( log k )} for Vertex Multiway Cut, p^{O(1)} k^{O(log k)} for Vertex Multicut with p requests and |Γ|^{O(1)} k^{O( log k)} for Group Feedback Vertex Set, where k is the deletion budget and Γis a finite group. Our first kernelization result, in particular, resolves an open question by Wahlström [ACM Transactions on Algorithms 2022], which was reiterated in a recent survey on kernelization by Jansen [Computer Science Reviews 2026]. Also, to the best of our knowledge, our kernel for Vertex Multicut is the first one whose size is completely polynomial in p and (quasi-polynomial) super-polynomial only in k. Finally, again using our vertex multicut-mimicking network for graphs, we obtain a hyperedge multicut-mimicking network for hypergraphs, which preserves hypergraph edge-multicuts of size up to c, of size |T|^{O(1)} c^{O(log c)}. Our result removes the dependence on the rank of the hypergraph from the exponent of the size bound, that existed in prior work.

0.29

Counting Paths and Trees via Exterior Algebra

cs.DS ·2026-09-13 ·Fahad Panolan, Saket Saurabh, Meirav Zehavi, Jie Xue
similarity 0.63
Abstract · Counting k-paths, Counting k-trees, Exterior Algebra

We give randomized approximation algorithms for counting k-paths and k-forests in a host graph. Here k denotes the number of pattern vertices, n and m denote the numbers of host vertices and edges or arcs, ε is the relative error, and δ is the failure probability. Our main results are: 1. Paths: We approximate the number of directed paths on $k$ vertices in $2^k k^{O(1)}(n+m)\varepsilon^{-2}\log(2/δ)$ arithmetic operations. 2. Trees and forests: For every fixed $η>0$, we approximate the number of non-induced copies of a given forest on $k$ vertices in $(2+η)^k n^{O_η(1)}\varepsilon^{-2}\log(2/δ)$ arithmetic operations. Our path algorithm resolves a conjecture of Koutis and Williams~[CACM 2016] and answers an open question of Lokshtanov, Saurabh, and Zehavi~[SODA 2021] by giving a $2^k poly(n,\varepsilon^{-1})$-time approximation scheme. Our algorithms combine exterior algebra with random matrix estimators, using the tensor-train moment bound of Rakhshan and Rabusseau~[AISTATS 2020]. For forests, we use a small-component separator to evaluate the estimator efficiently.

0.04

Improved polynomial-time algorithms for detecting and recovering planted $Θ(\sqrt{n})$-cliques

cs.DS math.ST ·2026-09-21 ·Dmitriy Kunisky, Songtao Mao
similarity 0.63
Abstract · 77 pages

In the planted clique problem, one observes either an Erdős--Rényi graph on $n$ vertices or such a graph with a clique added to $k = k(n)$ vertices, and seeks to detect or recover the clique. It is widely believed that $k = Θ(\sqrt{n})$ is the smallest clique size for which polynomial-time algorithms exist for these tasks. We develop new algorithms in this regime using color-coding to estimate signed subgraph counts, further accelerated with fast matrix multiplication. We first show that, for each $t \geq 1$, for $c(t)$ a constant associated to the order of growth of the number of connected graphs of treewidth at most $t$, cliques of size $k = λ\sqrt{n}$ planted in a random location with $λ> 1 / \sqrt{c(t)}$ can be detected and recovered in time $n^{t + 1 + o(1)}$. For instance, since $c(1) = e$, this recovers by counting signed trees the performance of the $\widetilde{O}(n^2)$-time message-passing algorithm of Deshpande--Montanari (2015) that succeeds when $λ> 1 / \sqrt{e} \approx 0.6066$. For $t \geq 3$, the exact value of $c(t)$ is not known, but lower bounds on it give a hierarchy of slower polynomial-time algorithms that succeed for smaller $λ$. We further show that the above algorithm for $t = 2$ can be implemented in time $n^{ω+ o(1)}$ for $ω$ the constant of square matrix multiplication and succeeds when $λ> 0.3320$; under the folklore conjecture that $ω= 2$, this runs in the nearly-linear time of the algorithm of Deshpande--Montanari while finding smaller cliques. Second, we show that the above algorithm for $t = 1$ can be combined with the boosting scheme of Alon--Krivelevich--Sudakov (1998) using rectangular matrix multiplication, giving improved runtimes for smaller $λ$. Taken together, our results achieve the best known tradeoff between runtime and signal strength $λ$.

0.27