Research map / Learning theory and algorithms / Submodular and game algorithms
An Exercise in Tournament Design: When Some Matches Must Be Scheduled
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies Demand-TF, a single-elimination tournament design problem where a set of demanded matches must be scheduled via seeding, giving NP-hardness, ETH and quasi-polynomial lower bounds, a 3^n and 2^n algorithm, and XP/FPT algorithms parameterized by feedback arc set number.
Problem
Designing a single-elimination tournament bracket (seeding) so that a given set of demand matches (desired matchups) all take place, a variant of Tournament Fixing.
Approach
Reduces scheduling demanded matches to a spanning binomial arborescence with prescribed demand arcs, and shows polynomial-time solvability when the tournament has constant feedback arc set number via guessing feedback-vertex parents and heights, compactness of heights, and a greedy packing subroutine.
Key results
- Demand-TF is NP-complete, even when all demand arcs share a common vertex; no n^{d^{O(1)}} algorithm unless NP is in quasi-P.
- Demand-TF can be solved in 3^n n^{O(1)} time (and 2^n n^{O(1)} with subset convolution), matching a 2^{o(n)} lower bound under ETH up to subexponential factors.
- Demand-TF is solvable in n^{O(k)} time where k is the feedback arc set number, and FPT in k when all upsets are demand matches.
Limitations
- Whether the problem is FPT parameterized by feedback arc set number remains open
- Maximizing the number of satisfied demand matches is not resolved in polynomial-in-d XP time
- Hardness and algorithms are theoretical; no empirical evaluation
Experimental setup
Builds on: Tournament Fixing spanning binomial arborescence characterization exponential time hypothesis
Closest papers by meaning
- Rigging Nearly Acyclic Tournaments Is Fixed-Parameter Tractable (AAAI 2017 · similarity 0.91)
- Adaptive Manipulation for Coalitions in Knockout Tournaments (AAAI 2025 · similarity 0.90)
- A Matching-Based Algorithm for the Traveling Tournament Problem (AAAI 2025 · similarity 0.86)
- How to Make Knockout Tournaments More Popular? (AAAI 2024 · similarity 0.84)
- Active Ranking and Matchmaking, with Perfect Matchings (ICML 2024 · similarity 0.83)
- Safe and Robust Subgame Exploitation in Imperfect Information Games (ICML 2024 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.