  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"
(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
difficulties. 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\'asz
(Open Problem 27 in Schrijver's book ``Combinatorial Optimization''). On the
other hand, we provide an efficient algorithm to the closely related and
well-studied Minimum-weight Odd $T$-Join problem for non-negative weights: our
algorithm runs in FPT time parameterized by $c$, where $c$ is the number of
connected components in some efficiently computed minimum-weight $T$-join. If
negative weights are also allowed, then finding a minimum-weight odd
$\{s,t\}$-join is equivalent to the Minimum-weight Odd $T$-Join problem for
arbitrary weights, whose complexity is still only conjectured to be
polynomial-time solvable. The analogous problems for digraphs are also
considered.
