Finding forest-orderings of tournaments is NP-complete
Abstract
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ős-Hajnal property.
Fields of Study & Subjects
Artificial Intelligence in Games
AI-based Problem Solving and Planning
Publication details
- Journal / source
- Discrete Mathematics & Theoretical Computer Science
- Volume
- vol. 28:2
- Issue
- Graph Theory
- Publication date
- 21 July 2026
- Language
- EN