Inhalt des Dokuments
The Minimum Shared Edges Problem on Grid-like Graphs
Meike Hatzel (TU Berlin)
The talk is about the NP-hard Minimum Shared Edges (MSE) problem on graphs, which is to decide whether it is possible to route p paths from a start vertex to a target vertex in a given graph while using at most k edges more than once. We present an arithmetic criterion to decide MSE on bounded (i.e. finite) grids in linear time when both dimensions are either small or large compared to the number p of paths. On the contrary, we also present that MSE remains NP-hard on subgraphs of bounded grids by giving a reduction of a Vertex Cover version. Finally, we also consider MSE from a parametrised complexity point of view. It is known that MSE is fixed-parameter tractable with respect to the number p of paths. We show that, under standard complexity-theoretical assumptions, the problem parametrised by the combined parameter k, p, maximum degree, diameter, and treewidth does not admit a polynomial-size problem kernel, even when restricted to planar graphs.
This is joint work with Till Fluschnik, Steffen Härtlein, Hendrik Molter, and Henning Seidler.
Back to the research colloquium site.