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.
