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:

@techreport{egres-20-15,

AUTHOR | = | {Frank, Andr{\'a}s and Hajdu, Gergely}, |

TITLE | = | {Simple algorithm and min-max formula for the inverse arborescence problem}, |

NOTE | = | {{\tt www.cs.elte.hu/egres}}, |

INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |

YEAR | = | {2020}, |

NUMBER | = | {TR-2020-15} |