7
$\begingroup$

Consider a non-directed graph. I want to find as many non-adjacent paths as possible from a source $s$ to a destination $t$. Two paths $P_1$ and $P_2$ are said to be non-adjacent to each other if none of the nodes in $P_1$ is a neighbor of any node in $P_2$.

Is this problem related to some standard problem in Graph theory?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ If you put it this way, it is quite similar to Menger's theorem. But only one direction is immediate. We can bound from above the number of such paths by $min_{C} \alpha(C)$ where $C$ is a set of vertices that cuts $s$ from $t$. The other direction does not seem to be that easy, and it might happen that in your problem we can not achieve this upper bound. $\endgroup$
    – Daniel Soltész
    Commented Jun 27, 2014 at 11:14
  • $\begingroup$ This is certainly different from Menger's Theorem. For example in $K_n$, we can find $n-1$ internally disjoint paths from $s$ to $t$, but only two such paths (the edge $st$ and some other path) in the above sense. $\endgroup$
    – Tony Huynh
    Commented Jun 27, 2014 at 11:40

2 Answers 2

Reset to default
2
$\begingroup$

This is an answer that was a comment before. I left the content of the comment, because it was leading to the answer.

The problem is NP-complete. The content of the comment:

As I mentioned earlier in the comments, an immediate upper bound to the number of such paths is $$\min_{C \subset V(G)} \alpha(C)$$ where $C$ cuts $s$ from $t$. But the following example shows that we can not always achieve this bound: graph .

As there are three vertex disjoint paths from $s$ to $t$, Menger's theorem says that every vertex cut contains at least three vertices. This graph without $s$ and $t$ is triangle-free, so for every cut $C$ the independence number $\alpha(C)$ is at least $2$. But we can have only one path from $s$ to $t$ as desired. (If we want two paths we can not use 2 or 5, but if we can not use them, there is only a single path.)

The proof of NP-completeness: The problem of finding an independent set of size $k$ can be reduced to this problem. Consider a graph $G$ and add two additional vertices $s$ and $t$, connect them both with every vertex of $G$. Now the maximal number of non-adjacent paths is $\alpha(G)$. Thus computing it efficiently is considered one of the hardest tasks.

Improve this answer
$\endgroup$
0
$\begingroup$

I think this is what you are looking for.

EDIT: as pointed out in the comments, Menger's Theorem actually only gives an upper bound on the sought-after number.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ That will do disjoint paths, but here there is the stronger requirement that the vertices are non-adjacent. There might be a way of using max-flow-min-cut type arguments, but it's not immediately clear. $\endgroup$
    – Ben Barber
    Commented Jun 27, 2014 at 10:46
  • $\begingroup$ Thanks for your comments. As Ben pointed out, the requirement of stronger non-adjacentment is essential in the problem. $\endgroup$
    – lchen
    Commented Jun 27, 2014 at 10:57

You must log in to answer this question.

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