The number of k-arc acyclic subdigraphs in which every vertex can reach a fixed root is independent of the root, for any balanced digraph.
On the complexity of counting feedback arc sets
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
In this note we study the computational complexity of feedback arc set counting problems in directed graphs, highlighting some subtle yet common properties of counting classes. Counting the number of feedback arc sets of cardinality $k$ and the total number of feedback arc sets are #P-complete problems, while counting the number of minimum feedback arc sets is only proven to be #P-hard. Indeed, this latter problem is #.OptP[log n]-complete, hence if it belongs to #P then P=NP.
fields
math.CO 1years
2025 1verdicts
ACCEPT 1representative citing papers
citing papers explorer
-
An equality for balanced digraphs
The number of k-arc acyclic subdigraphs in which every vertex can reach a fixed root is independent of the root, for any balanced digraph.