2026-07-20T05:09:03Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5632 2024-03-06T10:36:46Z ddc:004 open_access

The Parameterized Complexity of the Minimum Shared Edges Problem Fluschnik, Till Kratsch, Stefan Niedermeier, Rolf Sorge, Manuel Parameterized complexity kernelization treewidth treewidth reduction 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 is a subset of 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]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Till Fluschnik and Stefan Kratsch and Rolf Niedermeier and Manuel Sorge 2015 Is Part Of LIPIcs, Volume 45, 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2015.448 urn:nbn:de:0030-drops-56323 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2015.448 eng https://creativecommons.org/licenses/by/3.0/legalcode