Pierre Aboulker ; Guillaume Aubian ; Raul Lopes - Finding forest-orderings of tournaments is NP-complete

dmtcs:14281 - Discrete Mathematics & Theoretical Computer Science, July 21, 2026, vol. 28:2 - https://doi.org/10.46298/dmtcs.14281
Finding forest-orderings of tournaments is NP-completeArticle

Authors: Pierre Aboulker ; Guillaume Aubian ; Raul Lopes

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.


Volume: vol. 28:2
Section: Graph Theory
Published on: July 21, 2026
Accepted on: March 21, 2026
Submitted on: September 17, 2024
Keywords: Combinatorics

Consultation statistics

This page has been seen 83 times.
This article's PDF has been downloaded 37 times.