Finding forest-orderings of tournaments is NP-complete

Pierre Aboulker; Guillaume Aubian; Raul Lopes

doi:10.46298/dmtcs.14281

Article

Finding forest-orderings of tournaments is NP-complete

Pierre Aboulker⁽¹⁾, Guillaume Aubian⁽²⁾, Raul Lopes⁽³⁾

(1) École Normale Supérieure - PSL [ENS]

(2) Charles University

(3) Laboratoire d'Informatique, de Robotique et de Microélectronique de Montpellier [LIRMM]

Download article

Open on arXiv

Submitted on

September 17, 2024

Accepted on

March 21, 2026

Published on

July 21, 2026

Last modified on

July 21, 2026

Volume 28

vol. 28:2

Graph Theory

DOI

10.46298/dmtcs.14281

License

Attribution 4.0 International (CC BY 4.0)

French National Research Agency (ANR)

ANR-20-CE48-0008

Exploring the Limits of Tractability

Indicators

148

Views

Downloads

Finding forest-orderings of tournaments is NP-complete

Pierre Aboulker⁽¹⁾, Guillaume Aubian⁽²⁾, Raul Lopes⁽³⁾

(1) École Normale Supérieure - PSL [ENS]

(2) Charles University

(3) Laboratoire d'Informatique, de Robotique et de Microélectronique de Montpellier [LIRMM]

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.

Keywords

Combinatorics

Preview

Loading PDF preview...

References

P. Aboulker, G. Aubian, P. Charbit, and R. Lopes. Clique number of tournaments, 2023. Preprint available at arXiv:2310.04265.
DOI : 10.48550/arXiv.2310.04265
P. Aboulker, G. Aubian, P. Charbit, and S. Thomassé. Personal communication. 2023.
DOI : 10.37236/11838
F. N. Abu-Khzam. A kernelization algorithm for d-hitting set. Journal of Computer and System Sciences, 76(7):524-531, 2010.
DOI : 10.1016/j.jcss.2009.09.002
N. Ailon, M. Charikar, and A. Newman. Aggregating inconsistent information: Ranking and clus- tering. Journal of the ACM, 55(5), 2008.
DOI : 10.1145/1411509.1411513
N. Alon, J. Pach, and J. Solymosi. Ramsey-type theorems with forbidden subgraphs. Combinatorica, 21(2):155-170, 2001.
DOI : 10.1007/s004930100016
G. Aubian. Computing the clique number of tournaments, 2024. Preprint available at arXiv:2401.07776.
DOI : 10.48550/arXiv.2401.07776
J. Bang-Jensen and G. Gutin. Digraphs: Theory, Algorithms and Applications. Springer, London, 2007.
DOI : 10.1007/978-1-84800-998-1
E. Berger, K. Choromanski, M. Chudnovsky, J. Fox, M. Loebl, A. Scott, P. Seymour, and S. Thomass. Tournaments and colouring. Journal of Combinatorial Theory, Series B, 103:120, 2013.
DOI : 10.1016/j.jctb.2012.08.003
E. Berger, K. Choromanski, M. Chudnovsky, and S. Zerbib. Tournaments and the strong ErdősHajnal property. European Journal of Combinatorics, 100:103440, 2022.
DOI : 10.1016/j.ejc.2021.103440
S. Bessy, F. V. Fomin, S. Gaspers, C. Paul, A. Perez, S. Saurabh, and S. Thomass. Kernels for feedback arc set in tournaments. Journal of Computer and System Sciences, 77(6):1071-1078, 2011.
DOI : 10.1016/j.jcss.2010.10.001
D. Bokal, G. Fijavz, M. Juvan, P. Kayll, and B. Mohar. The circular chromatic number of a digraph. Journal of Graph Theory, 46:227 -240, 07 2004.
DOI : 10.1002/jgt.20003
P. Charbit, S. Thomassé, and A. Yeo. The minimum feedback arc set problem is NP-hard for tourna- ments. Combinatorics, Probability & Computing, 16:1-4, 2007.
DOI : 10.1017/s0963548306007887
X. Chen, X. Hu, and W. Zang. A min-max theorem on tournaments. SIAM Journal on Computing, 37(3):923-937, 2007.
DOI : 10.1137/060649987
M. Chudnovsky, A. Scott, P. Seymour, and S. Spirkl. Pure pairs. X. tournaments and the strong Erdős-Hajnal property. European Journal of Combinatorics, 115:103786, 2024.
DOI : 10.1016/j.ejc.2023.103786
W. W. Cohen, R. E. Schapire, and Y. Singer. Learning to order things. In Proc. of the 10th Advances in Neural Information Processing Systems (NIPS), volume 10. MIT Press, 1997.
M. Dom, D. Lokshtanov, and S. Saurabh. Incompressibility through colors and ids. In Proc. of the 36th International Colloquium on Automata, Languages and Programming (ICALP), pages 378- 389, 2009.
DOI : 10.1007/978-3-642-02927-132
C. Dwork, R. Kumar, M. Naor, and D. Sivakumar. Rank aggregation revisited. 2002. URL https: //api.semanticscholar.org/CorpusID:13976791.
M. El-Zahar and P. Erdős. On the existence of two non-neighboring subgraphs in a graph. Combinatorica, 5(4):295-300, 1985.
DOI : 10.1007/bf02579243
P. Erdős and A. Hajnal. On spanned subgraphs of graphs. Beitrage zur Graphentheorie und deren Anwendungen, Kolloq. Oberhof (DDR), 1977.
F. Fomin, D. Lokshtanov, V. Raman, and S. Saurabh. Fast local search algorithm for weighted feedback arc set in tournaments. Proc. of the 24th AAAI Conference on Artificial Intelligence (AAAI), 24(1):65-70, 2010.
DOI : 10.1609/aaai.v24i1.7557
A. Harutyunyan, T. Le, S. Thomassé, and H. Wu. Coloring tournaments: From local to global. Journal of Combinatorial Theory, Series B, 138:166-171, 2019.
DOI : 10.1016/j.jctb.2019.01.005
J. Kemeny. Mathematics without numbers. Daedalus, 88:571-590, 1959.
J. Kemeny and J. Snell. Mathematical Models in the Social Sciences. Blaisdell, 1962.
C. Kenyon-Mathieu and W. Schudy. How to rank with few errors. In Proc. of the 39th ACM Symposium on Theory of Computing (STOC), pages 95-103, 2007.
DOI : 10.1145/1250790.1250806
F. Klingelhoefer and A. Newman. Bounding the chromatic number of dense digraphs by arc neigh- borhoods. Combinatorica, 44(4):881895, 2024.
DOI : 10.1007/s00493-024-00098-z
F. Klingelhoefer and A. Newman. Coloring tournaments with few colors: Algorithms and complex- ity. SIAM Journal on Discrete Mathematics, 38(4):3111-3133, 2024.
DOI : 10.1137/23m1602127
T. Nguyen, A. Scott, and P. Seymour. On a problem of El-Zahar and Erdős. Journal of Combinatorial Theory, Series B, 165:211-222, 2024.
DOI : 10.1016/j.jctb.2023.11.004
T. Nguyen, A. Scott, and P. Seymour. Some results and problems on tournament structure. Journal of Combinatorial Theory, Series B, 173:146-183, 2025.
DOI : 10.1016/j.jctb.2025.02.002
T. Nguyen, A. Scott, and P. Seymour. Induced subgraph density. VI. bounded VC-dimension. Ad- vances in Mathematics, 482(A):110601, 2025.
DOI : 10.1016/j.aim.2025.110601
V. Raman and S. Saurabh. Parameterized algorithms for feedback set problems and their duals in tournaments. Theoretical Computer Science, 351(3):446-458, 2006.
DOI : 10.1016/j.tcs.2005.10.010
A. Scott and P. Seymour. A survey of χboundedness. Journal of Graph Theory, 95, 2020.
DOI : 10.1002/jgt.22601
S. Seshu and M. B. Reed. Linear Graphs and Electrical Networks. Addison-Wesley, 1961.
P. Slater. Inconsistencies in a schedule of paired comparisons. Biometrika, 48:303-312, 1961.
DOI : 10.1093/biomet/48.3-4.303
E. Speckenmeyer. On feedback problems in digraphs. In Nagl, M. (ed.) Graph-Theoretic Concepts in Computer Science. WG 1989. Lecture Notes in Computer Science, vol 411. Springer, Berlin, Heidelberg, pages 218-231, 1990.
DOI : 10.1007/3-540-52292-1_16
S. Zayat. Forests and the strong Erdős-Hajnal property. Discrete Mathematics, 347(5):113920, 2024.
DOI : 10.1016/j.disc.2024.113920
S. Zayat and S. Ghazal. Tournaments and the Erdős-Hajnal conjecture. Australasian Journal of Combinatorics, 86(2):351-372, 2023.
DOI : 10.1007/s00373-023-02643-x

Finding forest-orderings of tournaments is NP-complete

Pierre Aboulker⁽¹⁾, Guillaume Aubian⁽²⁾, Raul Lopes⁽³⁾

(1) École Normale Supérieure - PSL [ENS]

(2) Charles University

(3) Laboratoire d'Informatique, de Robotique et de Microélectronique de Montpellier [LIRMM]

Download article

Open on arXiv

Submitted on

September 17, 2024

Accepted on

March 21, 2026

Published on

July 21, 2026

Last modified on

July 21, 2026

Volume 28

vol. 28:2

Graph Theory

DOI

10.46298/dmtcs.14281

License

Attribution 4.0 International (CC BY 4.0)

French National Research Agency (ANR)

ANR-20-CE48-0008

Exploring the Limits of Tractability

Indicators

148

Views

Downloads

Finding forest-orderings of tournaments is NP-complete

Pierre Aboulker⁽¹⁾, Guillaume Aubian⁽²⁾, Raul Lopes⁽³⁾

(1) École Normale Supérieure - PSL [ENS]

(2) Charles University

(3) Laboratoire d'Informatique, de Robotique et de Microélectronique de Montpellier [LIRMM]

Abstract

Keywords

Combinatorics

Preview

Loading PDF preview...

References

P. Aboulker, G. Aubian, P. Charbit, and R. Lopes. Clique number of tournaments, 2023. Preprint available at arXiv:2310.04265.
DOI : 10.48550/arXiv.2310.04265
P. Aboulker, G. Aubian, P. Charbit, and S. Thomassé. Personal communication. 2023.
DOI : 10.37236/11838
F. N. Abu-Khzam. A kernelization algorithm for d-hitting set. Journal of Computer and System Sciences, 76(7):524-531, 2010.
DOI : 10.1016/j.jcss.2009.09.002
N. Ailon, M. Charikar, and A. Newman. Aggregating inconsistent information: Ranking and clus- tering. Journal of the ACM, 55(5), 2008.
DOI : 10.1145/1411509.1411513
N. Alon, J. Pach, and J. Solymosi. Ramsey-type theorems with forbidden subgraphs. Combinatorica, 21(2):155-170, 2001.
DOI : 10.1007/s004930100016
G. Aubian. Computing the clique number of tournaments, 2024. Preprint available at arXiv:2401.07776.
DOI : 10.48550/arXiv.2401.07776
J. Bang-Jensen and G. Gutin. Digraphs: Theory, Algorithms and Applications. Springer, London, 2007.
DOI : 10.1007/978-1-84800-998-1
E. Berger, K. Choromanski, M. Chudnovsky, J. Fox, M. Loebl, A. Scott, P. Seymour, and S. Thomass. Tournaments and colouring. Journal of Combinatorial Theory, Series B, 103:120, 2013.
DOI : 10.1016/j.jctb.2012.08.003
E. Berger, K. Choromanski, M. Chudnovsky, and S. Zerbib. Tournaments and the strong ErdősHajnal property. European Journal of Combinatorics, 100:103440, 2022.
DOI : 10.1016/j.ejc.2021.103440
S. Bessy, F. V. Fomin, S. Gaspers, C. Paul, A. Perez, S. Saurabh, and S. Thomass. Kernels for feedback arc set in tournaments. Journal of Computer and System Sciences, 77(6):1071-1078, 2011.
DOI : 10.1016/j.jcss.2010.10.001
D. Bokal, G. Fijavz, M. Juvan, P. Kayll, and B. Mohar. The circular chromatic number of a digraph. Journal of Graph Theory, 46:227 -240, 07 2004.
DOI : 10.1002/jgt.20003
P. Charbit, S. Thomassé, and A. Yeo. The minimum feedback arc set problem is NP-hard for tourna- ments. Combinatorics, Probability & Computing, 16:1-4, 2007.
DOI : 10.1017/s0963548306007887
X. Chen, X. Hu, and W. Zang. A min-max theorem on tournaments. SIAM Journal on Computing, 37(3):923-937, 2007.
DOI : 10.1137/060649987
M. Chudnovsky, A. Scott, P. Seymour, and S. Spirkl. Pure pairs. X. tournaments and the strong Erdős-Hajnal property. European Journal of Combinatorics, 115:103786, 2024.
DOI : 10.1016/j.ejc.2023.103786
W. W. Cohen, R. E. Schapire, and Y. Singer. Learning to order things. In Proc. of the 10th Advances in Neural Information Processing Systems (NIPS), volume 10. MIT Press, 1997.
M. Dom, D. Lokshtanov, and S. Saurabh. Incompressibility through colors and ids. In Proc. of the 36th International Colloquium on Automata, Languages and Programming (ICALP), pages 378- 389, 2009.
DOI : 10.1007/978-3-642-02927-132
C. Dwork, R. Kumar, M. Naor, and D. Sivakumar. Rank aggregation revisited. 2002. URL https: //api.semanticscholar.org/CorpusID:13976791.
M. El-Zahar and P. Erdős. On the existence of two non-neighboring subgraphs in a graph. Combinatorica, 5(4):295-300, 1985.
DOI : 10.1007/bf02579243
P. Erdős and A. Hajnal. On spanned subgraphs of graphs. Beitrage zur Graphentheorie und deren Anwendungen, Kolloq. Oberhof (DDR), 1977.
F. Fomin, D. Lokshtanov, V. Raman, and S. Saurabh. Fast local search algorithm for weighted feedback arc set in tournaments. Proc. of the 24th AAAI Conference on Artificial Intelligence (AAAI), 24(1):65-70, 2010.
DOI : 10.1609/aaai.v24i1.7557
A. Harutyunyan, T. Le, S. Thomassé, and H. Wu. Coloring tournaments: From local to global. Journal of Combinatorial Theory, Series B, 138:166-171, 2019.
DOI : 10.1016/j.jctb.2019.01.005
J. Kemeny. Mathematics without numbers. Daedalus, 88:571-590, 1959.
J. Kemeny and J. Snell. Mathematical Models in the Social Sciences. Blaisdell, 1962.
C. Kenyon-Mathieu and W. Schudy. How to rank with few errors. In Proc. of the 39th ACM Symposium on Theory of Computing (STOC), pages 95-103, 2007.
DOI : 10.1145/1250790.1250806
F. Klingelhoefer and A. Newman. Bounding the chromatic number of dense digraphs by arc neigh- borhoods. Combinatorica, 44(4):881895, 2024.
DOI : 10.1007/s00493-024-00098-z
F. Klingelhoefer and A. Newman. Coloring tournaments with few colors: Algorithms and complex- ity. SIAM Journal on Discrete Mathematics, 38(4):3111-3133, 2024.
DOI : 10.1137/23m1602127
T. Nguyen, A. Scott, and P. Seymour. On a problem of El-Zahar and Erdős. Journal of Combinatorial Theory, Series B, 165:211-222, 2024.
DOI : 10.1016/j.jctb.2023.11.004
T. Nguyen, A. Scott, and P. Seymour. Some results and problems on tournament structure. Journal of Combinatorial Theory, Series B, 173:146-183, 2025.
DOI : 10.1016/j.jctb.2025.02.002
T. Nguyen, A. Scott, and P. Seymour. Induced subgraph density. VI. bounded VC-dimension. Ad- vances in Mathematics, 482(A):110601, 2025.
DOI : 10.1016/j.aim.2025.110601
V. Raman and S. Saurabh. Parameterized algorithms for feedback set problems and their duals in tournaments. Theoretical Computer Science, 351(3):446-458, 2006.
DOI : 10.1016/j.tcs.2005.10.010
A. Scott and P. Seymour. A survey of χboundedness. Journal of Graph Theory, 95, 2020.
DOI : 10.1002/jgt.22601
S. Seshu and M. B. Reed. Linear Graphs and Electrical Networks. Addison-Wesley, 1961.
P. Slater. Inconsistencies in a schedule of paired comparisons. Biometrika, 48:303-312, 1961.
DOI : 10.1093/biomet/48.3-4.303
E. Speckenmeyer. On feedback problems in digraphs. In Nagl, M. (ed.) Graph-Theoretic Concepts in Computer Science. WG 1989. Lecture Notes in Computer Science, vol 411. Springer, Berlin, Heidelberg, pages 218-231, 1990.
DOI : 10.1007/3-540-52292-1_16
S. Zayat. Forests and the strong Erdős-Hajnal property. Discrete Mathematics, 347(5):113920, 2024.
DOI : 10.1016/j.disc.2024.113920
S. Zayat and S. Ghazal. Tournaments and the Erdős-Hajnal conjecture. Australasian Journal of Combinatorics, 86(2):351-372, 2023.
DOI : 10.1007/s00373-023-02643-x