Odd Paths, Cycles, and $T$-Joins: Connections and Algorithms

Source abstract

Abstract. Minimizing the weight of an edge set satisfying parity constraints is a challenging branch of combinatorial optimization as witnessed by the binary hypergraph chapter of Alexander Schrijver’s book [ Combinatorial Optimization, Springer-Verlag, 2003, Chapter 80]. This area contains relevant graph theory problems including open cases of the Max Cut problem and some multiflow problems. We clarify the interconnections between some of these problems and establish three levels of difficulty. On the one hand, we prove that the Shortest Odd Path problem in undirected graphs without cycles of negative total weight and several related problems are NP-hard, settling a long-standing open question asked by Lovász (Open Problem 27 in Schrijver’s book [ Combinatorial Optimization, Springer-Verlag, 2003]). On the other hand, we provide an algorithm for the closely related and well-studied Minimum-weight Odd [Formula: see text]-Join problem for nonnegative weights: our algorithm runs in FPT time parameterized by [Formula: see text], where [Formula: see text] is the number of connected components in some efficiently computed minimum-weight [Formula: see text]-join. If negative weights are also allowed, then finding a minimum-weight odd [Formula: see text]-join is equivalent to the Minimum-weight Odd [Formula: see text]-Join problem for arbitrary weights, whose complexity is still only conjectured to be polynomially solvable. The analogous problems for digraphs are also considered.