8
$\begingroup$

Suppose we have a graph where every edge is colored red or blue. We say that a path is alternating if the red and blue edges alternate in it. Our goal is to find many edge/vertex-disjoint alternating paths from a given vertex $s$ to another given vertex $t$. Has this problem been studied before?

Update: It DOES NOT seem to me ANYMORE that the following, Menger-type theorem is true, as pointed out by Ilya in the comments:

Lemma: We say that a partition of the vertices into $S, T, R, B$ is a colored cut if $s\in S, t\in T$, there are no edges between $S$ and $T$ and, except for the edges between $R$ and $B$, the vertices of $R$ are only adjacent to red edges and the vertices of $B$ are only adjacent to blue edges. There are $k$ edge/vertex-disjoint paths from $s$ to $t$ if and only if after deleting any $k-1$ edges/vertices, there is no colored cut.

Update: Gyula Pap told me that if we consider the directed version and edge-disjoint paths, then doubling every vertex (to redin-blueout and bluein-redout) reduces the problem to the monochromatic Menger's theorem from which (if I see well) the above lemma follows. So now I am mainly interested in the vertex-disjoint version.

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ Make a new uncolored graph whose edges represent a blue edge followed by a red edge in the original graph. So a path in the new graph is a $(RB)^*$ path in the original. Other possibilities like starting and finishing with the same colour can be handled; only 4 cases to do separately if necessary. Some fiddling might be needed to achieve the type of path disjointedness you require, but it looks promising. $\endgroup$
    – Brendan McKay
    Oct 2, 2011 at 12:27
  • 1
    $\begingroup$ Nice. I think you also mean to require that there are no edges directly between vertices in S and vertices in T (in the definition of colored cut). $\endgroup$
    – Hugh Thomas
    Oct 2, 2011 at 12:41
  • $\begingroup$ right Hugh, thx! $\endgroup$
    – domotorp
    Oct 2, 2011 at 13:53
  • 1
    $\begingroup$ @Brendan: You are right that your approach gives an equivalent formulation but I am not sure how easy it is to get nice theorems from it. Eg. the same way you can handle line graphs with a sentence and still there are many results about them. $\endgroup$
    – domotorp
    Oct 2, 2011 at 13:57
  • 1
    $\begingroup$ Do you allow a path to intersect itself? If not, then your condition is not a criterion. Consider a graph with blue edges $sx$, $xt$, $yz$ and red edges $xy$, $xz$. Then there is no colored cut, though no non-selfintersecting alternating path from $s$ to $t$. $\endgroup$
    – Ilya Bogdanov
    Oct 3, 2011 at 16:49

1 Answer 1

Reset to default
5
$\begingroup$

It seems that the problem of determining whether there exist $2$ vertex disjoint red-blue alternating paths joining vertices $s$ and $t$ is NP-complete. Thus, unless NP $=$ co-NP, there exist no efficient characterization of obstructions to existence of such paths, similar to the one you propose in the lemma.

Below is a reduction to the classical result of Fortune, Hopcroft and Wyllie that the DIRECTED $2$-LINKAGE problem is NP-complete. ( Given a digraph $D$ and four distinct vertices $u_1,v_1,u_2,v_2$; does $D$ contain a pair of vertex-disjoint paths $P_1, P_2$, so that $P_i$ is a directed path from $u_i$ to $v_i$ for $i=1,2$?)

Given a digraph $D$, we replace every directed edge $e=xy$ of $D$ by a vertex $w_e$ joined to $x$ by a red edge and to $y$ by a blue edge. Then we add vertex $s$ joined by a blue edge to $u_1$ and by a red edge to $v_2$, and a vertex $t$ joined by a blue edge to $u_2$ and a red edge to $v_1$. It is not hard to see that a pair of vertex disjoint paths from $s$ to $t$ in the new graph corresponds exactly to the $2$-linkage as described above.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Nice, thx a lot! $\endgroup$
    – domotorp
    Oct 12, 2011 at 21:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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