paper

A simplified min-max formula for the inverse arborescence problem

arXiv:2608.02496

Abstract

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.

6 pages, 1 figure