{"id":"arxiv/2608.02496","url":"https://arxiv.org/abs/2608.02496","tags":["math.CO"],"score":0,"title":"A simplified min-max formula for the inverse arborescence problem","domain":"math.CO","source":"arxiv","authors":["András Frank","Hanna Szabrina Horváth"],"reviews":0,"subject":"math.CO","summary":"A simple min-max theorem is formulated and proved for the smallest modification (measured in $l_1$-norm) of an input cost function $w_0$ that makes a target arborescence $F_0$ of a digraph a cheapest arborescence. The constructive proof gives rise to a polynomial time algorithm for computing both a minimizer cost function on the primal side and a maximizer dual object in the min-max formula.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-03","reactions":{}}