Questions tagged [disjoint-paths]
The disjoint-paths tag has no usage guidance.
10
questions
6
votes
0answers
102 views
Enumerating homologies of disjoint paths
I am reading this recent paper by Schrijver, in particular, section 4.2: Enumerating homologies of disjoint paths.
I did not understand how do they re-route the paths through a spanning tree and ...
9
votes
1answer
196 views
What is the best upper bound on the running time of the graph minor algorithm?
A cornerstone of the graph minor theory is an algorithm that, given undirected graphs $G, H$, runs in time $f(|H|)poly(|G|)$, and determines whether $H$ is a minor of $G$ or not. It has been obtained ...
3
votes
0answers
94 views
Homologous flows on planar graphs
I was reading this paper by A. Schrijver on "Finding k disjoint paths in directed planar graphs".
First they describe what are cohomologous functions on a graph. My interpretation of this definition ...
4
votes
1answer
126 views
Hardness of finding if a vertex lies on a simple directed path between two vertices
Given a directed graph $G = (V, E)$ and three vertices $u, v, w \in V$. Is it NP-Hard to find whether there is a simple path from $u$ to $v$ passing through $w$?
I found a couple of hardness ...
3
votes
1answer
138 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
149 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
530 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
676 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
256 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
468 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$-...
