Algorithm counts feedback vertex sets of all sizes faster than before
Counting Feedback Vertex Sets of All Sizes in Subexponential Time, Conditionally
Data Structures and Algorithms
Summary
A tough problem in graph theory is to count specific sets of points called feedback vertex sets, which help understand cycles in networks. The authors present a new method that counts how many of these sets there are for every possible size, doing so more efficiently than traditional approaches—though their speed depends on a certain computational hypothesis. Their approach also extends to counting other related structures like trees and paths within graphs. This could help in areas where understanding complex networks and their cycle structures is important.
What this means in practice
- •For network analysts: Count and analyze cycle-breaking sets across various sizes to better understand network reliability within complex graphs.
- •For circuit designers: Use efficient counting of feedback vertex sets to evaluate and optimize feedback loops in electronic circuit graphs.
A theory result. No direct application yet.
Authors
Mengyang Wu, Minghao Wang
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.