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

摘要: Given a graph $G=(V,E)$, two vertices $s,t\in V$, and integers $k,\ell$, the Short Secluded Path problem is to find simple $s$-$t$-path with at most $k$ $\ell$ neighbors. We study parameterized complexity of respect four structural parameters: vertex cover number, treewidth, feedback edge number. In particular, we completely settle question existence kernels size polynomial in these parameters their combinations $\ell$. also obtain $2^{O(w)}\cdot \ell^2\cdot n$-time algorithm for graphs treewidth $w$, which yields subexponential-time algorithms several classes.