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?

$\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$ 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
    Jun 27, 2014 at 11:40

2 Answers 2

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.

$\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.

$\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
    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
    Jun 27, 2014 at 10:57

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.