Rigging Nearly Acyclic Tournaments Is Fixed-Parameter Tractable

被引:0
作者
Ramanujan, M. S. [1 ]
Szeider, Stefan [1 ]
机构
[1] TU Wien, Algorithms & Complex Grp, Vienna, Austria
来源
THIRTY-FIRST AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE | 2017年
基金
奥地利科学基金会;
关键词
D O I
暂无
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
Single-elimination tournaments (or knockout tournaments) are a popular format in sports competitions that is also widely used for decision making and elections. In this paper we study the algorithmic problem of manipulating the outcome of a tournament. More specifically, we study the problem of finding a seeding of the players such that a certain player wins the resulting tournament. The problem is known to be NP-hard in general. In this paper we present an algorithm for this problem that exploits structural restrictions on the tournament. More specifically, we establish that the problem is fixed-parameter tractable when parameterized by the size of a smallest feedback arc set of the tournament (interpreting the tournament as an oriented complete graph). This is a natural parameter because most problems on tournaments (including this one) are either trivial or easily solvable on acyclic tournaments, leading to the question what about nearly acyclic tournaments or tournaments with a small feedback arc set? Our result significantly improves upon a recent algorithm by Aziz et al. (2014) whose running time is bounded by an exponential function where the size of a smallest feedback arc set appears in the exponent and the base is the number of players.
引用
收藏
页码:3929 / 3935
页数:7
相关论文
共 50 条
[41]   EXTENDING ORTHOGONAL PLANAR GRAPH DRAWINGS IS FIXED-PARAMETER TRACTABLE [J].
Bhore, Sujoy ;
Ganian, Robert ;
Khazaliya, Liana ;
Montecchiani, Fabrizio ;
Noellenburg, Martin .
JOURNAL OF COMPUTATIONAL GEOMETRY, 2024, 15 (02) :3-39
[42]   Fixed-parameter tractability results for feedback set problems in tournaments [J].
Dom, Michael ;
Guo, Jiong ;
Hueffner, Falk ;
Niedermeier, Rolf ;
Truss, Anke .
ALGORITHMS AND COMPLEXITY, PROCEEDINGS, 2006, 3998 :320-331
[43]   Directed Subset Feedback Vertex Set Is Fixed-Parameter Tractable [J].
Chitnis, Rajesh ;
Cygan, Marek ;
Hajiaghayi, Mohammataghi ;
Marx, Daniel .
ACM TRANSACTIONS ON ALGORITHMS, 2015, 11 (04)
[44]   When is Red-Blue Nonblocker Fixed-Parameter Tractable? [J].
Gaspers, Serge ;
Gudmundsson, Joachim ;
Horton, Michael ;
Ruemmele, Stefan .
LATIN 2018: THEORETICAL INFORMATICS, 2018, 10807 :515-528
[45]   Faster Fixed-Parameter Tractable Algorithms for Matching and Packing Problems [J].
M. R. Fellows ;
C. Knauer ;
N. Nishimura ;
P. Ragde ;
F. Rosamond ;
U. Stege ;
D. M. Thilikos ;
S. Whitesides .
Algorithmica, 2008, 52 :167-176
[46]   Directed Subset Feedback Vertex Set Is Fixed-Parameter Tractable [J].
Chitnis, Rajesh ;
Cygan, Marek ;
Hajiaghayi, Mohammadtaghi ;
Marx, Daniel .
AUTOMATA, LANGUAGES, AND PROGRAMMING, ICALP 2012 PT I, 2012, 7391 :230-241
[47]   Fixed-Parameter Tractability of Multicut in Directed Acyclic Graphs [J].
Kratsch, Stefan ;
Pilipczuk, Marcin ;
Pilipczuk, Michal ;
Wahlstroem, Magnus .
AUTOMATA, LANGUAGES, AND PROGRAMMING, ICALP 2012 PT I, 2012, 7391 :581-593
[48]   FIXED-PARAMETER TRACTABILITY OF MULTICUT IN DIRECTED ACYCLIC GRAPHS [J].
Kratsch, Stefan ;
Pilipczuk, Marcin ;
Pilipczuk, Michal ;
Wahlstroem, Magnus .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2015, 29 (01) :122-144
[49]   Fixed-parameter tractability results for feedback set problems in tournaments [J].
Dom, Michael ;
Guo, Jiong ;
Hueffner, Falk ;
Niedermeier, Rolf ;
Truss, Anke .
JOURNAL OF DISCRETE ALGORITHMS, 2010, 8 (01) :76-86
[50]   Faster fixed-parameter tractable algorithms for matching and packing problems [J].
Fellows, MR ;
Knauer, C ;
Nishimura, N ;
Ragde, P ;
Rosamond, F ;
Stege, U ;
Thilikos, DM ;
Whitesides, S .
ALGORITHMS ESA 2004, PROCEEDINGS, 2004, 3221 :311-322