Questions tagged [disjoint-paths]

The tag has no usage guidance.

4 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
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$. ...
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 ...
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 ...
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 ...