3 papers
cs.DM2026
Separating Feasibility and Movement in Solution Discovery: The Case of Path Discovery
Hanno von Bergen, Larissa Fastenau, Enna Gerhard +8
We study solution discovery, where the goal is to obtain a feasible solution to a problem from an initial configuration by a bounded sequence of local moves. In many applications,…
math.CO2025
Obstructions for normally spanned sets of vertices
Nicola Lorenz, Max Pitz
Halin conjectured that a graph has a normal spanning tree if and only if every minor of it has countable colouring number. This has recently been proven by the second author. In th…
cs.CC2025
Directed disjoint paths remains W[1]-hard on acyclic digraphs without large grid minors
Ken-ichi Kawarabayashi, Nicola Lorenz, Marcelo Garlet Milani +1
In the Vertex Disjoint Paths with Congestion problem, the input consists of a digraph , an integer and pairs of vertices , and the task is to find a set of p…