Towards Combinatorial Min-Max Relations from Extended Linear Programming Formulations - Silva, Marcel K. de Carli; Leston-Rey, Mario; Oliveira, Henri M. F.; Sato, Cristiane M. (Anais do Encontro de Teoria da Computação (ETC); 2025: Anais do X Encontro de Teoria da Computação, 2025)
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.