Ranking tournaments

被引：116

作者：

Alon, N ^{[1
]}

机构：

[1] Tel Aviv Univ, Raymond & Beverly Sackler Fac Exact Sci, Sch Math & Comp Sci, IL-69978 Tel Aviv, Israel

[2] IAS, Princeton, NJ 08540 USA

来源：

SIAM JOURNAL ON DISCRETE MATHEMATICS | 2006年 / 20卷 / 01期

关键词：

tournament; feedback arc set problem;

D O I：

10.1137/050623905

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

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.

引用

页码：137 / 142

页数：6

共 8 条

[1]

Ailon Nir, 2005, P 37 ANN ACM S THEOR, P684, DOI [10.1145/1060590.1060692, DOI 10.1145/1060590.1060692]

[2] Approximating the cut-norm via Grothendieck's inequality [J].

Alon, N ;

Naor, A .

SIAM JOURNAL ON COMPUTING, 2006, 35 (04) :787-803

[3] EIGENVALUES, GEOMETRIC EXPANDERS, SORTING IN ROUNDS, AND RAMSEY THEORY [J].

ALON, N .

COMBINATORICA, 1986, 6 (03) :207-219

[4]

Alon N., 2000, PROBABILISTIC METHOD

[5]

Alon Noga, 2004, Proc. of the 36th ACM STOC, P72, DOI 10.1145/1007352.1007371

[6]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness

[7]

Arora S., 1995, Proceedings of the Twenty-Seventh Annual ACM Symposium on the Theory of Computing, P284, DOI 10.1145/225058.225140

[8] A POLYNOMIAL ALGORITHM FOR THE 2-PATH PROBLEM FOR SEMICOMPLETE DIGRAPHS [J].

BANGJENSEN, J ;

THOMASSEN, C .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 1992, 5 (03) :366-376

← 1 →