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. 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). So, I am interested in what happends between these two extremes. If these kinds of problems have been studied before I would greatly appreciate a reference.