{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,2]],"date-time":"2026-04-02T17:21:42Z","timestamp":1775150502754,"version":"3.50.1"},"publisher-location":"California","reference-count":0,"publisher":"International Joint Conferences on Artificial Intelligence Organization","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019,8]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.24963\/ijcai.2019\/46","type":"proceedings-article","created":{"date-parts":[[2019,7,28]],"date-time":"2019-07-28T03:46:05Z","timestamp":1564285565000},"page":"322-328","source":"Crossref","is-referenced-by-count":2,"title":["On Succinct Encodings for the Tournament Fixing Problem"],"prefix":"10.24963","author":[{"given":"Sushmita","family":"Gupta","sequence":"first","affiliation":[{"name":"National Institute of Science Education and Research School of Computer Sciences (NISER), India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[{"name":"The Institute of Mathematical Sciences, HBNI, Chennai, India"},{"name":"University of Bergen, Norway"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ramanujan","family":"Sridharan","sequence":"additional","affiliation":[{"name":"University of Warwick, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Meirav","family":"Zehavi","sequence":"additional","affiliation":[{"name":"Ben Gurion University of the Negev, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"10584","event":{"name":"Twenty-Eighth International Joint Conference on Artificial Intelligence {IJCAI-19}","theme":"Artificial Intelligence","location":"Macao, China","acronym":"IJCAI-2019","number":"28","sponsor":["International Joint Conferences on Artificial Intelligence Organization (IJCAI)"],"start":{"date-parts":[[2019,8,10]]},"end":{"date-parts":[[2019,8,16]]}},"container-title":["Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence"],"original-title":[],"deposited":{"date-parts":[[2019,7,28]],"date-time":"2019-07-28T03:46:27Z","timestamp":1564285587000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ijcai.org\/proceedings\/2019\/46"}},"subtitle":[],"proceedings-subject":"Artificial Intelligence Research Articles","short-title":[],"issued":{"date-parts":[[2019,8]]},"references-count":0,"URL":"https:\/\/doi.org\/10.24963\/ijcai.2019\/46","relation":{},"subject":[],"published":{"date-parts":[[2019,8]]}}}