<p>Geelen and Kapadia appear to have a randomized algorithm for this problem.
<a href="http://arxiv.org/abs/1504.07647" rel="nofollow">http://arxiv.org/abs/1504.07647</a></p>

CC BY-SA 3.0
2014-11-11T17:37:32.373Z
2015-09-13T03:12:59.613Z
2015-09-13T03:12:59.613Z
Chandra Chekuri
<p>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.</p>

<p>It is well known that the following problem has a strongly polynomial time solution (<a href="http://www.springer.com/mathematics/applications/book/978-3-540-44389-6" rel="nofollow">Schrijver</a>, Theorem 29.1):</p>

<blockquote>
  <p>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.</p>
</blockquote>

<p>However, I am interested the complexity of the following problem:</p>

<blockquote>
  <p>Given a graph $G = (V,E)$, a weight function $w \in \mathbb{Q}^E$, and the vertex set $T \subseteq V$, find an <strong>odd</strong> (or even) $T$-join of minimum total weight.</p>
</blockquote>

<p>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.</p>

<p><a href="http://www.math.uwaterloo.ca/~bico/papers/kp.pdf" rel="nofollow">Cook, Espinoza, and Goycoolea</a> 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 <em>et al.</em> 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$.</p>

<p>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 <a href="http://www.springer.com/mathematics/applications/book/978-3-540-44389-6" rel="nofollow">Schrijver</a>. Note that the odd path and walk problems are <em>not</em> 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.</p>

<p>So in summary:</p>

<blockquote>
  <p>Is there a (strongly) polynomial time algorithm to find a minimum weight odd (or even) $T$-join? Is the problem NP-hard?</p>
</blockquote>

CC BY-SA 3.0
2014-05-16T23:28:40.153Z
Is there anything known about finding a given parity T-join for general T? Also for the optimization version when T=2 then the problem is somehow related to finding shortest 2 disjoint paths which is in RP. (Well I don't know how to prove it's as hard as that one because we can choose arbitrary vertex for a cycle as a source and terminal and check for all possible cases (relaxes situation) but on the other hand that cycle should have particular parity which seems make it harder). Finally what's a motivation for finding a shortest T-join of a given parity?
Saeed
CC BY-SA 3.0
2014-05-17T00:30:48.587Z
Finding some odd or even T-join is pretty simple. A graph contains a T-join if and only if each component contains an even number of members of T. Arbitrarily pair up vertices of T sharing a components and find paths between them. The symmetric difference of those paths is a T-join of either odd or even parity. The symmetric difference of any two T-joins is an edge-disjoint collection of cycles. So a T-join of the other parity exists if and only if the graph is not bipartite.
Kyle Fox
CC BY-SA 3.0
2014-05-17T00:41:02.840Z
@Saeed The problem appears related to computing maximum cuts in low genus graphs. I noticed the parity path and walk results and was surprised I could not find anything on parity T-joins. Not being forced to find a connected subgraph makes the problem appear easier somehow.
Kyle Fox
CC BY-SA 3.0
2014-05-17T14:02:51.763Z
Thanks for a cool idea for the first part. But about a latter, I cannot see why parity should be important in T-joins. I mean parity is usually useful for a coloring related problems (like perfect graphs, k-partite graphs, ...) but T-join is usually used for cuts and solving optimization problems (such as TSP, ...) which are mostly not related to parity. I mean I cannot see why parity should be important here? (BTW if you just enjoy is another thing, I was just curious).
Saeed
CC BY-SA 3.0
2014-05-19T14:32:25.437Z
@Saeed In surface embedded graphs, determining whether a set of edges is dual to a cut actually is a generalized parity question. For example, see [Chambers _et al_.](http://www.cs.uiuc.edu/~jeffe/pubs/surfcut.html). So a maximum cut would be dual to a maximum weight ø-join with the right generalized parity constraints. The question I posed here seems easier and I thought it sounded natural enough to have been studied for its own sake.
Kyle Fox
CC BY-SA 3.0
2014-10-28T11:49:00.790Z
Can you give a reference to the first claim ($T$-join edge set is poly-time solvable)? For $T=\emptyset$, This seems annoyingly similar to the NP-hard problem of (weighted) Eulerian Extension ([see here](http://www.akt.tu-berlin.de/fileadmin/fg34/publications-akt/euler_short.pdf)).
R B
CC BY-SA 3.0
2014-10-28T13:50:30.440Z
@RB I added a reference to Theorem 29.1 of Schrijver. These [notes](https://courses.engr.illinois.edu/cs598csc/sp2010/Lectures/Lecture13.pdf) describe how to solve minimum weight T-join via a reduction to minimum weight perfect matching.
Kyle Fox
<cc.complexity-theory><graph-algorithms>
What is the complexity of minimum weight odd T-join?
Kyle Fox
# What is the complexity of minimum weight odd T-join?

(Asked by: username_0 on 2014-05-16)

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](http://www.springer.com/mathematics/applications/book/978-3-540-44389-6), 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](http://www.math.uwaterloo.ca/~bico/papers/kp.pdf) 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](http://www.springer.com/mathematics/applications/book/978-3-540-44389-6). 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?

**Tags:** cc.complexity-theory, graph-algorithms
> **Comments:**
> **username_1**: Is there anything known about finding a given parity T-join for general T? Also for the optimization version when T=2 then the problem is somehow related to finding shortest 2 disjoint paths which is in RP. (Well I don't know how to prove it's as hard as that one because we can choose arbitrary vertex for a cycle as a source and terminal and check for all possible cases (relaxes situation) but on the other hand that cycle should have particular parity which seems make it harder). Finally what's a motivation for finding a shortest T-join of a given parity?  
> **username_0**: Finding some odd or even T-join is pretty simple. A graph contains a T-join if and only if each component contains an even number of members of T. Arbitrarily pair up vertices of T sharing a components and find paths between them. The symmetric difference of those paths is a T-join of either odd or even parity. The symmetric difference of any two T-joins is an edge-disjoint collection of cycles. So a T-join of the other parity exists if and only if the graph is not bipartite.  
> **username_0**: @Saeed The problem appears related to computing maximum cuts in low genus graphs. I noticed the parity path and walk results and was surprised I could not find anything on parity T-joins. Not being forced to find a connected subgraph makes the problem appear easier somehow.  
> **username_1**: Thanks for a cool idea for the first part. But about a latter, I cannot see why parity should be important in T-joins. I mean parity is usually useful for a coloring related problems (like perfect graphs, k-partite graphs, ...) but T-join is usually used for cuts and solving optimization problems (such as TSP, ...) which are mostly not related to parity. I mean I cannot see why parity should be important here? (BTW if you just enjoy is another thing, I was just curious).  
> **username_0**: @Saeed In surface embedded graphs, determining whether a set of edges is dual to a cut actually is a generalized parity question. For example, see [Chambers _et al_.](http://www.cs.uiuc.edu/~jeffe/pubs/surfcut.html). So a maximum cut would be dual to a maximum weight ø-join with the right generalized parity constraints. The question I posed here seems easier and I thought it sounded natural enough to have been studied for its own sake.  
> **username_2**: Can you give a reference to the first claim ($T$-join edge set is poly-time solvable)? For $T=\emptyset$, This seems annoyingly similar to the NP-hard problem of (weighted) Eulerian Extension ([see here](http://www.akt.tu-berlin.de/fileadmin/fg34/publications-akt/euler_short.pdf)).  
> **username_0**: @RB I added a reference to Theorem 29.1 of Schrijver. These [notes](https://courses.engr.illinois.edu/cs598csc/sp2010/Lectures/Lecture13.pdf) describe how to solve minimum weight T-join via a reduction to minimum weight perfect matching.  

---

## 1 answers

### Answer by username_3 on 2014-11-11. Score: 4

Geelen and Kapadia appear to have a randomized algorithm for this problem.
<http://arxiv.org/abs/1504.07647>


---

