Questions tagged [disjoint-paths]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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$-...