# Find multiple non-adjacent paths in a graph

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?

• 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. Jun 27, 2014 at 11:14
• 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. Jun 27, 2014 at 11:40

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: .

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.

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.

• 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. Jun 27, 2014 at 10:46
• Thanks for your comments. As Ben pointed out, the requirement of stronger non-adjacentment is essential in the problem. Jun 27, 2014 at 10:57