Let $G=(V,E)$ be an undirected graph and let $T \subseteq V$. A subset $J$ of $E$ is called a $T$-join if $T$ is equal to the set of vertices of odd degree in the graph $(V, J)$. Further $J$ is an odd (even) $T$-join if it contains an odd (even) number of edges.
It is well known that the following problem has a strongly polynomial time solution (Schrijver, Theorem 29.1):
Given a graph $G = (V,E)$, a weight function $w \in \mathbb{Q}^E$, and the vertex set $T \subseteq V$, find a $T$-join of minimum total weight.
However, I am interested the complexity of the following problem:
Given a graph $G = (V,E)$, a weight function $w \in \mathbb{Q}^E$, and the vertex set $T \subseteq V$, find an odd (or even) $T$-join of minimum total weight.
The problem is still interesting even if we assume all edge weights are non-negative. In fact, efficient algorithms for both the odd and even case with non-negative weights would imply efficient algorithms for both cases with negative weights.
Cook, Espinoza, and Goycoolea describe an $O(2^{|T|} + |T|^2|V|^2 + |V|^3)$ time algorithm for a slight variation on the problem where edges are colored red and blue and you want an odd number of red edges. The colored variant is equivalent though simple reductions. Unlike the algorithms for minimum weight $T$-join that ignore parity, the algorithm by Cook et al. takes time exponential in $|T|$. Also, their algorithm depends upon the weights being non-negative, as the reduction to the non-negative case could increase the cardinality of $T$.
Also, there are strongly polynomial time algorithms for finding shortest simple $s,t$-paths with an odd number of edges, and shortest $s,t$-walks with an odd number of edges that do not repeat any edges. Again, these algorithms assume non-negative weights. Both are described by Schrijver. Note that the odd path and walk problems are not special cases of the odd $T$-join problem where $|T| = 2$. A minimum weight odd $T$-join with $T = \{s,t\}$ could contain an even $s,t$-path and an odd cycle as separate components.
So in summary:
Is there a (strongly) polynomial time algorithm to find a minimum weight odd (or even) $T$-join? Is the problem NP-hard?
