3 papers
math.CO2026
Optimal Bounds for the k-Disjoint Paths Problem
Dario Cavallaro, Maximilian Gorsky, Stephan Kreutzer +2
The Graph Minors Series of Robertson and Seymour forms the foundation of algorithmic structural graph theory, yielding fixed-parameter algorithms for problems such as Disjoint Path…
cs.DM2025
Well-Quasi-Ordering Eulerian Digraphs Embeddable in Surfaces by Strong Immersion
Dario Cavallaro, Ken-ichi Kawarabayashi, Stephan Kreutzer
We prove that for every surface , the class of Eulerian directed graphs that are Eulerian embeddable into (in particular they have degree at most ) is well-quasi-ordere…
cs.DM2025
The Directed Disjoint Paths Problem with Congestion
Matthias Bentert, Dario Cavallaro, Amelie Heindl +3
The classic result by Fortune, Hopcroft, and Wyllie [TCS~'80] states that the directed disjoint paths problem is NP-complete even for two pairs of terminals. Extending this well-kn…