MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $S:=$ { $s_i : i \in [k]$ } and $T:=$ { $t_i : i \in [k]$ } be disjoint subsets of vertices of a graph $G$. Furthermore, let $A$ be a subset of $S_k$ (the symmetric group on $[k]$). A set of disjoint paths $\mathcal{P}:=$ { $P_1, \dots P_k$ } is $A$-feasible, if there exists $\pi \in A$ such that $P_i$ connects $s_i$ with $t_{\pi(i)}$ for all $i \in [k]$.

Problem: Given $S, T$, and $A$ with $k$ fixed, is there a polynomial-time algorithm to test if a graph has an $A$-feasible set of $S$-$T$ paths?

Motivation. Actually, the answer to the question is yes, but let me better explain what I am looking for. The case $A=S_k$ is easy. Menger's theorem gives us an exact characterization, and network flow theory gives us an efficient algorithm. On the other hand the case $|A|=1$ is quite difficult. There is indeed a polynomial-time algorithm, but it uses most of the machinery from the graph minors papers of Robertson and Seymour (see Graph Minors XIII). Once we know that it is true for $|A|=1$, then we have a polynomial-time algorithm by enumerating over all $\pi \in A$ and running the algorithm from Graph Minors XIII. However, this is rather unsatisfactory since there is such a nice algorithm when $A=S_k$. So, I am interested in what happens between these two extremes. If these kinds of problems have been studied before I would greatly appreciate a reference.

share|cite|improve this question
It would also be good if the running time depended on something like log |A| when A is "nice" (like a subgroup)... the thing you propose has dependence |A|, I think? – Dave Pritchard Sep 23 '10 at 8:54

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.