×

zbMATH — the first resource for mathematics

The minimum feedback arc set problem is NP-hard for tournaments. (English) Zbl 1120.05038
The authors show that the problem of determining the minimum number of arcs in a tournament whose reversal yields an acyclic tournament is NP-hard. This settles a conjecture of J. Bang-Jensen and C. Thomassen [SIAM J. Discrete Math. 5, 366–376 (1992; Zbl 0759.05041)]. The conjecture has also been settled by N. Alon [SIAM J. Discrete Math. 20, 137–142 (2006; Zbl 1112.05043)].

MSC:
05C20 Directed graphs (digraphs), tournaments
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
PDF BibTeX XML Cite
Full Text: DOI