direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

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.

Till Fluschnik
TEL 512

Back to the research colloquium site.

Zusatzinformationen / Extras