5
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Saeed May 16 '14 at 23:28
  • $\begingroup$ 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. $\endgroup$ – Kyle Fox May 17 '14 at 0:30
  • $\begingroup$ @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. $\endgroup$ – Kyle Fox May 17 '14 at 0:41
  • $\begingroup$ 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). $\endgroup$ – Saeed May 17 '14 at 14:02
  • $\begingroup$ @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.. 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. $\endgroup$ – Kyle Fox May 19 '14 at 14:32
4
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.