Shortest Odd Paths in Undirected Graphs with Conservative Weight Functions

Jüttner, Alpár and Király, Csaba and Mendoza-Cadena, Lydia Mirabel and Pap, Gyula and Schlotter, Ildikó and Yamaguchi, Yutaro (2024) Shortest Odd Paths in Undirected Graphs with Conservative Weight Functions. DISCRETE APPLIED MATHEMATICS : THE JOURNAL OF COMBINATORIAL ALGORITHMS, INFORMATICS AND COMPUTATIONAL SCIENCES, 357. pp. 34-50. ISSN 0166-218X (print); 1872-6771 (online)

Preview

Text 1-s2.0-S0166218X24002324-main.pdf Available under License Creative Commons Attribution Non-commercial. Download (523kB) | Preview

Abstract

We consider the Shortest Odd Path 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 Shortest Odd Path problem had been open for 20 years, and was recently shown to be NP-hard. We give a polynomial-time algorithm for the special case when the weight function is conservative and the set E − of negative-weight edges forms a single tree. Our algorithm exploits the strong connection between Shortest Odd Path and the problem of finding two internally vertex-disjoint paths between two terminals in an undirected edge-weighted graph. It also relies on solving an intermediary problem variant called Shortest Parity-Constrained Odd Path where for certain edges we have parity constraints on their position along the path. Also, we exhibit two FPT algorithms for solving Shortest Odd Path. The first FPT algorithm is parameterized by |E−|, the number of negative edges, or more generally, by the maximum size of a matching in the subgraph of G spanned by E −, when the weight function is conservative. Our second FPT algorithm is parameterized by the treewidth of G, and the algorithm does not rely on conservativeness.

Actions (login required)

Edit Item