Simple algorithm and min-max formula for the inverse arborescence problem

András Frank, Gergely Hajdu


In 1998, Hu and Liu developed a strongly polynomial algorithm for solving the inverse arborescence problem that aims at modifying minimally a given cost-function on the edge-set of a digraph so that an input arborescence becomes a cheapest one. In this note, we develop a conceptually simpler algorithm along with a min-max theorem for the minimum modification of the cost-function. The approach is based on a link to a min-max theorem and a 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.

Bibtex entry:

AUTHOR = {Frank, Andr{\'a}s and Hajdu, Gergely},
TITLE = {Simple algorithm and min-max formula for the inverse arborescence problem},
NOTE= {{\tt}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2020},
NUMBER = {TR-2020-15}

Last modification: 29.12.2020. Please email your comments to Tamás Király!