PTAS for feedback arc set in tournaments

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

A finite tournament is an orientation of a complete graph. A feedback arc set $F$ is a set of arcs such that deleting $F$ leaves no directed cycle. Define $\operatorname{OPT}(T)=\min\{|F|:F\text{ is a feedback arc set of }T\}$. A polynomial-time approximation scheme permits a running-time exponent depending on a fixed approximation parameter $\epsilon>0$.

Statement recorded in the supplied source.

For each $\epsilon>0$, is there an algorithm that, on every $n$-vertex tournament $T$, runs in time polynomial in $n$ (for that fixed $\epsilon$) and returns a feedback arc set $F$ satisfying $|F|\leq(1+\epsilon)\operatorname{OPT}(T)$? [S2]

Short English statement

Does the tournament feedback-arc problem have a polynomial-time algorithm for every fixed desired relative accuracy?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 3291 (OPG-47646). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, PTAS for feedback arc set in tournaments, node 47646, original problem page. Original question and full discussion. https://www.openproblemgarden.org/op/ptas_for_feedback_arc_set_in_tournaments.