The parameterized complexity of the minimum shared edges problem

摘要

We study the NP-complete Minimum Shared Edges (MSE) problem, defined as follows. Given an undirected graph, a source and a sink vertex, and two integers p and k, we ask 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. On the positive side, we show that MSE is fixed-parameter tractable with respect to p. On the negative side, 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, and that MSE does not admit a polynomial-size kernel with respect to p (unless NP⊆coNP/poly).