Random Explorations in Algorithms for Feedback Set Problems on Tournaments

Every pair of players meets exactly once in a tournament, and a directed cycle is a set of results that no ranking can explain. How few players (Feedback Vertex Set) or matches (Feedback Arc Set) must be thrown out to make the results fit some ranking? I survey parameterized algorithms for both.

A tournament has a cycle exactly when it has a directed triangle, which leads to simple branching and a natural link to 3-Hitting Set. For Feedback Arc Set, two reduction rules give a quadratic kernel, and chromatic coding (a random coloring with about √(8k) colors, followed by dynamic programming) gives a subexponential 2^{O(√k log k)} n^O(1) algorithm.