# Questions tagged [disjoint-paths]

The tag has no usage guidance.

6 questions
Filter by
Sorted by
Tagged with
631 views

I'm interested in the following problem. We're given as input a "target permutation" $\sigma\in S_n$, as well as an ordered list of indices $i_1,\ldots,i_m\in [n-1]$. Then, starting with the list $L=... 0answers 489 views ### Simple path on dag with backward edges What is the complexity of the following problem ($\in$P? NP-hard?): Input: a directed acyclic graph$D=(V,E)$, a set of backward edges$E'\subset V\times V$, and two distinct nodes$s$and$t$. ... 1answer 142 views ### Label-disjoint paths in directed graphs Checking if there are two edge-disjoint paths from$s$to$t$in a given undirected graph$G$is in P via a standard solution based on maxflow. I am interested in the complexity of the following ... 1answer 255 views ### For which values of$k$is minimum length undirected$k$-disjoint-paths in$\mathcal{P}$? In a related question, Saeed and Super8 have mentioned the Robertson-Seymour theory which enables us to find$k$disjoint paths between pairs of vertices$\{s_i,t_i\}_{i=1}^k$in poly time for fixed$...
A replacement path is a simple path allocated to an edge $e \in G$ that connects the endpoints of $e$ in $G \setminus \{e\}$. The problem An undirected graph $G$ is given and the task is to allocate ...
### For which values of $k$ is the $k$-disjoint paths problem in $\mathcal{P}$?
The $k$-Vertex-Disjoint Paths Problem ($k$-$\text{DPP}$) is defined as follows: Input: A graph $G=(V,E)$ and $k$ pairs of vertices $(s_1,t_1),\ldots,(s_k,t_k)$. Question: Does there exist $k$-...