Questions tagged [disjoint-paths]
The disjoint-paths tag has no usage guidance.
6
questions
3
votes
1answer
124 views
Mutually exclusive replacement paths, an existing problem?
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 ...
7
votes
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 ...
10
votes
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$.
...
10
votes
1answer
631 views
Probability of generating a desired permutation by random swaps
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=...
4
votes
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 $...
2
votes
2answers
358 views
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$-...
