Given a class of (undirected) graphs $\mathcal{ C}$, we say that a Feedback Arc Set (FAS for short) $F$ is a $\mathcal{ C}$-FAS if the graph induced by the edges of $F$ (forgetting their orientations) belongs to $\mathcal{ C}$. We show that deciding if a tournament has a $\mathcal{ C}$-FAS is NP-complete when $\mathcal{ C}$ is the class of all forests. We are motivated by connections between $\mathcal{ C}$-FAS and structural parameters of tournaments, such as the dichromatic number, the clique number of tournaments, and the strong Erd\H{ o}s-Hajnal property.
Categories: math.CO