#

### Volume 2022

#### Article 1

Published by the Department of Computer Science, The University of Chicago.

#### 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)
**BibTeX** entry for this
article (304 bytes)

Submitted September 29,2020, revised March 10, 2022,published March 26, 2022.

Volume 2020, Article 4
Article 2

Volume 2022
Published articles