Ranking tournaments with no errors

Abstract

As various combinatorial optimization problems can be formulated as integer linear programs, polyhedral and linear programming approaches have turned out to be essential and powerful tools for studying these problems. By applying linear programming theory and polyhedral characterization, often, one can determine the polynomial-time solvability of the optimization problems and obtain elegant combinatorial consequences, e.g., min-max theorems.

This thesis is devoted to studying the classical combinatorial optimization problem of ranking a set of players on the basis of a set of pairwise comparisons arising from a sports tournament; the objective is to minimize the total number of upsets, where an {\em upset} occurs if a higher ranked player was actually defeated by a lower ranked player. This problem can be rephrased as the so-called minimum feedback arc set problem on tournaments. Let $T = (V,A)$ be a tournament with a nonnegative integral weight $w(e)$ on each arc $e$. A subset $F$ of arcs is called a {\em feedback arc set} (FAS) if $T\backslash F$ contains no cycles (directed). The {\em minimum-weight FAS problem on tournaments}, denoted by FAST, is to find an FAS in the input tournament $T$ with minimum total weight.

In 2006, Alon showed that the unweighted version of the FAST ($\bm{w}$ is the all-one vector) is in fact {\em NP}-hard. In 2007, Mathieu and Schudy devised a polynomial time approximation scheme (PTAS) for the FAST. Given these results, it is natural to ask the following question: When can the FAST be solved exactly in polynomial time? Inspired by the title of Mathieu and Schudy's paper, this is equivalent to asking: Which tournaments can be ranked with no errors? The main concern of this thesis is to resolve this \emph{NP}-hard problem using polyhedral and linear programming approaches.

A collection ${\cal C}$ of cycles (with repetition allowed) is called a {\em cycle packing} if each arc $e$ is used at most $w(e)$ times by members of ${\cal C}$. We call a tournament $T=(V,A)$ {\em cycle Mengerian} (CM) if, for any nonnegative integral function $\bm{w}$ defined on $A$, the minimum total weight of a feedback arc set is equal to the maximum size of a cycle packing. The main purpose of this thesis is to present a structural characterization of all CM tournaments, which yields a polynomial-time algorithm for the FAST on such tournaments.