2026/08/03 by András Frank, Hanna Szabrina Horváth · 1 voice
Mathematics · #math.CO #msc:90C27 #msc:90C47 #msc:90C46
6 pages, 1 figure
arxiv created 2026/08/03 · arxiv updated 2026/08/04
A simple min-max theorem is formulated and proved for the smallest modification (measured in l1-norm) of an input cost function w0 that makes a target arborescence F0 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.