Ranking tournaments

Research output: Contribution to journalArticlepeer-review

157 Scopus citations


A tournament is an oriented complete graph. The feedback arc set problem for tournaments is the optimization problem of determining the minimum possible number of edges of a given input tournament T whose reversal makes T acyclic. Ailon, Charikar, and Newman showed that this problem is NP-hard under randomized reductions. Here we show that it is in fact NP-hard. This settles a conjecture of Bang-Jensen and Thomassen.

Original languageEnglish (US)
Pages (from-to)137-142
Number of pages6
JournalSIAM Journal on Discrete Mathematics
Issue number1
StatePublished - 2006
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • General Mathematics


  • Feedback arc set problem
  • Tournament


Dive into the research topics of 'Ranking tournaments'. Together they form a unique fingerprint.

Cite this