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
    Commented 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
    Commented Oct 2, 2011 at 12:41
  • $\begingroup$ right Hugh, thx! $\endgroup$
    – domotorp
    Commented 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
    Commented 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
    Commented 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
    Commented Oct 12, 2011 at 21:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .