Ranking tournaments

Noga Alon

doi:10.1137/050623905

Ranking tournaments

Noga Alon

Research output: Contribution to journal › Article › peer-review

161 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 language	English (US)
Pages (from-to)	137-142
Number of pages	6
Journal	SIAM Journal on Discrete Mathematics
Volume	20
Issue number	1
DOIs	https://doi.org/10.1137/050623905
State	Published - 2006
Externally published	Yes

All Science Journal Classification (ASJC) codes

General Mathematics

Keywords

Feedback arc set problem
Tournament

Access to Document

10.1137/050623905

Cite this

@article{948313c4c848462d8be26c1712012c31,

title = "Ranking tournaments",

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.",

keywords = "Feedback arc set problem, Tournament",

author = "Noga Alon",

year = "2006",

doi = "10.1137/050623905",

language = "English (US)",

volume = "20",

pages = "137--142",

journal = "SIAM Journal on Discrete Mathematics",

issn = "0895-4801",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "1",

}

TY - JOUR

T1 - Ranking tournaments

AU - Alon, Noga

PY - 2006

Y1 - 2006

N2 - 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.

AB - 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.

KW - Feedback arc set problem

KW - Tournament

UR - http://www.scopus.com/inward/record.url?scp=33746043842&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33746043842&partnerID=8YFLogxK

U2 - 10.1137/050623905

DO - 10.1137/050623905

M3 - Article

AN - SCOPUS:33746043842

SN - 0895-4801

VL - 20

SP - 137

EP - 142

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

IS - 1

ER -

Ranking tournaments

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this