{"id":"arxiv/2607.20996","url":"https://arxiv.org/abs/2607.20996","tags":["math.CO","math.PR"],"score":0,"title":"The optimal constant for minimum weight feedback arc sets in oriented graphs","domain":"math.CO","source":"arxiv","authors":["Yacong Zhou"],"reviews":0,"subject":"math.CO","summary":"Let $D$ be an oriented graph (a digraph with no directed 2-cycles) with maximum degree $Δ\\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Δ}})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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-23","reactions":{}}