On Succinct Encodings for the Tournament Fixing Problem

On Succinct Encodings for the Tournament Fixing Problem

Sushmita Gupta, Saket Saurabh, Ramanujan Sridharan, Meirav Zehavi

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence
Main track. Pages 322-328. https://doi.org/10.24963/ijcai.2019/46

Single-elimination tournaments are a popular format in competitive environments. The Tournament Fixing Problem (TFP), which is the problem of finding a seeding of the players such that a certain player wins the resulting tournament, is known to be NP-hard in general and fixed-parameter tractable when parameterized by the feedback arc set number of the input tournament (an oriented complete graph) of expected wins/loses. However, the existence of polynomial kernelizations (efficient preprocessing) for TFP has remained open. In this paper, we present the first polynomial kernelization for TFP parameterized by the feedback arc set number of the input tournament. We achieve this by providing a polynomial-time routine that computes a SAT encoding where the number of clauses is bounded polynomially in the feedback arc set number.
Keywords:
Agent-based and Multi-agent Systems: Computational Social Choice
Agent-based and Multi-agent Systems: Voting