Sie sind hier

# The Parameterized Complexity of Finding Paths with Shared Edges

Till Fluschnik (TU Berlin)

We study the so-called Minimum Shared Edges problem on undirected graphs. Given anundirected graph, a source and a sink vertex, and two integers $p$ and $k$, the question is whether there are $p$ paths in the graph connecting the source with the sink that share at most $k$ edges. Herein, an edge is shared if it appears in at least two paths.Complementing an NP-hardness result for the directed variant, we show that the problem is NP-complete. Moreover, we show that it remains NP-complete on graphs of maximum degree five. Further we show that the problem is W[2]-hard when parameterized by the number of shared edges and that it is fixed-parameter tractable when parameterized by the number of paths. For the latter result, we employ the so-called treewidth reduction technique due to Marx et al. (ACM TALG 2013) and we provide a dynamic program that, given a tree decomposition of the input graph, solves the problem in FPT-time with respect to the number of paths and the width of the tree decomposition.

Date
Speaker
Location
Language
21.05.2015
16:15
Till Fluschnik
TEL 512
english

Back to the research colloquium site.