Shortest Odd path on undirected graphs with conservative weights.

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.