Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|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
add comment

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.