The optimal constant for minimum weight feedback arc sets in oriented graphs

Abstract

Let $D$ be an oriented graph (a digraph with no directed 2-cycles) with maximum degree $\hat{I}”\ge 1$, equipped with nonnegative arc weights of total weight $w(D)$, and let ${\mathrm{fas}}_w(D)$ denote the minimum weight of a feedback arc set of $D$. Alon (2002) proved ${\mathrm{fas}}_w(D)\le (\frac{1}{2}-\frac{1}{16\sqrt{2\hat{I}”}})w(D)$. We determine the optimal constant: \[\mathrm{fas}_w(D)\le(\frac{1}{2}-\frac{\sqrt{2}}{6\sqrtΔ})w(D).\] In fact, we show a stronger result: ${\mathrm{fas}}_w(D)\le \frac{1}{2}w(D)-\frac{\sqrt{2}}{12}{\sum }_v{w}_2(v)$, where $w_2(v)$ is the ${\ell }_2$-norm of the weights of the arcs incident with $v$. Both bounds are attained by the unit-weight directed triangle, so the constant $\sqrt{2}/6$ is best possible (already among unweighted oriented graphs). The proof combines the vertex-peeling scheme of Berger and Shor with a continuous random-ordering analysis: realizing the random order by independent uniform labels renders the expected local imbalance at each vertex exactly an integrated Khintchine-type functional, and the theorem reduces to the sharp evaluation \[\inf_{\|a\|_2=1}\int_0^1 \mathbb{E}|\sum_j a_j B_j(q)|\,dq = \frac{\sqrt{2}}{6},\] where the $B_j(q)$ are i.i.d. Bernoulli$(q)$ random variables, which we prove via Fourier analysis. The proof also yields a randomized, near-linear-time algorithm attaining the bounds in expectation.

17 pages, 0 figures