### Volume 2022

#### Complexity of counting feedback vertex sets

Kévin Perrot
Laboratoire d'Informatique et Systèmes, Aix-Marseille Univeristé,
France
kevin DOT perrot AT lis-lab DOT fr

March 26, 2022

#### 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$.

• The article: PDF (836 KB)
• Source material: ZIP (68 KB)