## René van Bevern, Till Fluschnik, and Oxana Yu. Tsidulko.
Parameterized algorithms and data reduction for the short secluded
*s*-*t*-path problem.
*Networks*, 75(1):34–63, 2020.

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 ℓ.

[ bib |
DOI |
http ]
Back

*This file was generated by
bibtex2html 1.99.*