Towards Combinatorial Min-Max Relations from Extended Linear Programming Formulations

We study the concept of extended total dual integrality and the combinatorial min-max relations that can be derived from this notion. In this work, we prove the extended total dual integrality property for compact extended linear programming formulations for the minimum-cost r-arborescence problem and the maximum-weight perfectly matchable subset problem. From this, we derive dual integer programming problems and show how to solve each pair of primal-dual problems algorithmically and efficiently by adapting classical methods. We also provide a combinatorial interpretation to the dual problem of the minimum-cost r-arborescence problem as a distance splitting problem.