Speaker:  Mirabel Mendoza
Center for Mathematical Modeling, U. de Chile
Date: Monday, March 31, 2025 at 2:30 p.m. Santiago time

Abstract:  

We consider the Shortest Odd Path (SOP) problem, where given an undirected graph $G$, a weight function on its edges, and two vertices $s$ and $t$ in $G$, the aim is to find an $(s,t)$-path with odd length and, among all such paths, of minimum weight. For the case when the weight function is conservative, i.e., when every cycle has non-negative total weight, the complexity of the SOP problem had been open for 20 years, and was recently shown to be NP-hard. I’ll present a polynomial-time algorithm for the special case when the weight function is conservative and the set of negative-weight edges forms a single tree. The algorithm exploits the strong connection between SOP and the problem of finding two internally vertex-disjoint paths between two terminals in an undirected edge-weighted graph. This is a joint work with Alpár Jüttner, Csaba Király, Gyula Pap, Ildikó Schlotter, and Yutaro Yamaguchi.

Venue: John Von Neumann Seminar Room, CMM, Beauchef 851, North Tower, 7th Floor