# Questions tagged [disjoint-paths]

The tag has no usage guidance.

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