5
$\begingroup$

Let $k\in\mathbb N$. Given a finite graph with two subsets of vertices $X$ and $Y$, Menger's Theorem gives a criterion for when there are $k$ pairwise disjoint paths starting in $X$ and ending in $Y$.

Now let $X_1$, $Y_1$, $\dots$,$X_k$, $Y_k$ be subsets of vertices. Is there a "similar" condition for when there are $k$ pairwise disjoint paths, one path starting in $X_1$ and ending in $Y_1$, a second path starting in $X_2$ and ending in $Y_2$, $\dots$, and a $k^{\text {th}}$ path starting in $X_k$ and ending in $Y_k$?

$\endgroup$
1
  • 1
    $\begingroup$ Perhaps, if you copied M's theorem here (into your "Question"), there'd be a better chance to get an answer. $\endgroup$
    – Wlod AA
    Oct 19 at 4:47
10
$\begingroup$

There is no known necessary and sufficient condition like in Menger's theorem.

However, there is a polynomial-time algorithm that decides if the paths exist. This is one of the main results of the Graph Minors Project of Robertson and Seymour (see Graph Minors XIII). The algorithm is quite involved and uses many of the results from the graph minors series. Robertson and Seymour solve the problem when each $X_i$ and $Y_i$ have size $1$, but your problem can be reduced to this case by shrinking each $X_i$ and each $Y_i$ to a single vertex.

The $k=2$ case (with $|X_1|=|X_2|=|Y_1|=|Y_2|=1$) has a nice necessary and sufficient condition for $4$-connected graphs. The required paths do not exist if and only if $G$ is planar and $X_1, X_2, Y_1, Y_2$ occur in this cyclic order on the outerface of $G$. This was proved independently by Thomassen and Seymour.

No necessary and sufficient conditions are known for $k \geq 3$.

$\endgroup$
2
  • $\begingroup$ A nice answer (+1). ######### The meaning of word condition has to be narrowed down before the OP's question makes any sense. $\endgroup$
    – Wlod AA
    Oct 19 at 5:34
  • $\begingroup$ @Tony Huynh: Thank you. $\endgroup$
    – Tri
    Oct 19 at 6:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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