A simplified min-max formula for the inverse arborescence problem

András Frank; Hanna Szabrina Horváth

A simplified min-max formula for the inverse arborescence problem

András Frank, Hanna Szabrina Horváth

arXivarxiv/2608.02496Aug 3, 2026math.COscore 0

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.

Source JSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2608.02496
curl -X POST /api/v1/records/arxiv/2608.02496/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.02496/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'