Parameterized algorithms and data reduction for the short secluded s-t-path problem

06/25/2018
by   René van Bevern, et al.
0

Given a graph G=(V,E), two vertices s,t∈ V, and two integers k,ℓ, we search for a simple s-t-path with at most k vertices and at most ℓ neighbors. For graphs with constant crossing number, we provide a subexponential 2^O(√(n))-time algorithm, prove a matching lower bound, and show a polynomial-time data reduction algorithm that reduces any problem instance to an equivalent instance (a so-called problem kernel) of size polynomial in the vertex cover number of the input graph. In contrast, we show that the problem in general graphs is hard to preprocess. We obtain a 2^O(ω)·ℓ^2· n-time algorithm for graphs of treewidth ω, show that there is no problem kernel with size polynomial in ω, yet show a problem kernels with size polynomial in the feedback edge number of the input graph and with size polynomial in the feedback vertex number, k, and ℓ.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset