A simple algorithm and min–max formula for the inverse arborescence problem
András Frank, Gergely Hajdu · Discrete Applied Mathematics · 2021
In 1998, Hu and Liu developed a strongly polynomial algorithm for solving the inverse arborescence problem that aims at minimally modifying a given cost-function on the edge-set of a digraph D so that an input spanning arborescence of D becomes a cheapest one. In this note, we develop a conceptually simpler algorithm along with a new min–max formula for the minimum modification of the cost-function. The approach is based on a link to a min–max theorem and a simple (two-phase greedy) algorithm by the first author from 1979 concerning the primal optimization problem of finding a cheapest subgraph of a digraph that covers an intersecting family along with the corresponding dual optimization problem, as well.