Ranking tournaments

Research output: Contribution to journalArticle

128 Scopus citations

Abstract

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
Volume20
Issue number1
DOIs
StatePublished - Dec 1 2006
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

Keywords

  • Feedback arc set problem
  • Tournament

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

  • Cite this