Parameterized algorithms and data reduction for the short secluded $s$-$t$-path problem. van Bevern, R., Fluschnik, T., & Tsidulko, O. Networks, 75(1):34-63, 2020.
Parameterized algorithms and data reduction for the short secluded $s$-$t$-path problem [link]Preprint  doi  abstract   bibtex   
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 ℓ.
@article{BFT20,
  author =	 {Ren{\'{e}} van Bevern and Till Fluschnik and Oxana
                  Tsidulko},
  title =	 {Parameterized algorithms and data reduction for the
                  short secluded $s$-$t$-path problem},
  journal =	 {Networks},
  year =	 2020,
  date =	 {2020-01-01},
  volume =	 {75},
  number =	 {1},
  pages =	 {34-63},
  url_Preprint = {https://arxiv.org/abs/1806.09540},
  doi =		 {10.1002/net.21904},
  abstract =	 {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 ℓ.}
}

Downloads: 0