Ranking tournaments
N Alon - SIAM Journal on Discrete Mathematics, 2006 - SIAM
SIAM Journal on Discrete Mathematics, 2006•SIAM
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.
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.
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.
Society for Industrial and Applied Mathematics