direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

The Parameterized Complexity of the Minimum Shared Edges Problem

Till Fluschnik (TU Berlin)

We study the NP-complete Minimum Shared Edges (MSE) problem. Given an undirected 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 and sharing at most k edges. Herein, an edge is shared if it appears in at least two paths. We show that MSE is W[1]-hard when parameterized by the treewidth of the input graph and the number k of shared edges combined. We show that MSE is fixed-parameter tractable with respect to p, but does not admit a polynomial-size kernel (unless NP ⊆ coNP/poly). In the proof of the fixed-parameter tractability of MSE parameterized by p, we employ the treewidth reduction technique due to Marx, O’Sullivan, and Razgon [ACM TALG 2013].

The talk is based on a joint work with Stefan Kratsch, Rolf Niedermeier and Manuel Sorge.

Date
Speaker
Location
Language
03.12.2015
16:15
Till Fluschnik
TEL 512
English

 

Back to the research colloquium site. [1]

------ Links: ------

Zusatzinformationen / Extras