Menger's theorem with restrictions on where the paths can begin and end

Question

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$?

Answer 1

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