The shortest $k$-edge disjoint paths problem is defined as follows:

Input: An undirected graph $G=(V,E)$ and $k$ pairs of vertices $(s_1,t_1),\ldots,(s_k,t_k)$.

Question: Find (if exist) $k$-pairwise edge-disjoint paths $P_1,\ldots,P_k$ where $P_i$ goes from $s_i$ to $t_i$, such that $\sum\limits_{i=1}^k|P_i|$ is minimized, where $|P_i|$ denotes the number of edges in path $P_i$.

Is there a fixed-parameter tractable or an XP algorithm known for the problem, with parameter $k$ ?

PS: This is a related question: For which values of $k$ is minimum length undirected $k$-disjoint-paths in $\mathcal{P}$?.

  • 1
    $\begingroup$ IIRC I did some literature search for this some time ago and it seems to be open even for $k=3$. $\endgroup$
    – Laakeri
    May 22, 2022 at 7:04


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.