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

{"_id":"wvwib5ZZWjPs69ECW","bibbaseid":"vanbevern-fluschnik-tsidulko-parameterizedalgorithmsanddatareductionfortheshortsecludedstpathproblem-2020","authorIDs":["2fwXJtKDCNhaSNr5s"],"author_short":["van Bevern, R.","Fluschnik, T.","Tsidulko, O."],"bibdata":{"bibtype":"article","type":"article","author":[{"firstnames":["René"],"propositions":["van"],"lastnames":["Bevern"],"suffixes":[]},{"firstnames":["Till"],"propositions":[],"lastnames":["Fluschnik"],"suffixes":[]},{"firstnames":["Oxana"],"propositions":[],"lastnames":["Tsidulko"],"suffixes":[]}],"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 ℓ.","bibtex":"@article{BFT20,\n author =\t {Ren{\\'{e}} van Bevern and Till Fluschnik and Oxana\n Tsidulko},\n title =\t {Parameterized algorithms and data reduction for the\n short secluded $s$-$t$-path problem},\n journal =\t {Networks},\n year =\t 2020,\n date =\t {2020-01-01},\n volume =\t {75},\n number =\t {1},\n pages =\t {34-63},\n url_Preprint = {https://arxiv.org/abs/1806.09540},\n doi =\t\t {10.1002/net.21904},\n abstract =\t {Given a graph G=(V,E), two vertices s,t∈V, and two\n integers k,ℓ, we search for a simple s-t-path with\n at most k vertices and at most ℓ neighbors. For\n graphs with constant crossing number, we provide a\n subexponential 2^O(√n)-time algorithm, prove a\n matching lower bound, and show a polynomial-time\n data reduction algorithm that reduces any problem\n instance to an equivalent instance (a so-called\n problem kernel) of size polynomial in the vertex\n cover number of the input graph. In contrast, we\n show that the problem in general graphs is hard to\n preprocess. We obtain a 2^O(ω)⋅ℓ^2⋅n-time algorithm\n for graphs of treewidth ω, show that there is no\n problem kernel with size polynomial in ω, yet show a\n problem kernels with size polynomial in the feedback\n edge number of the input graph and with size\n polynomial in the feedback vertex number, k, and ℓ.}\n}\n\n","author_short":["van Bevern, R.","Fluschnik, T.","Tsidulko, O."],"key":"BFT20","id":"BFT20","bibbaseid":"vanbevern-fluschnik-tsidulko-parameterizedalgorithmsanddatareductionfortheshortsecludedstpathproblem-2020","role":"author","urls":{" preprint":"https://arxiv.org/abs/1806.09540"},"metadata":{"authorlinks":{"van bevern, r":"https://rvb.su/"}},"downloads":1,"html":""},"bibtype":"article","biburl":"http://rvb.su/rvb.bib","creationDate":"2021-01-06T14:24:56.572Z","downloads":1,"keywords":[],"search_terms":["parameterized","algorithms","data","reduction","short","secluded","path","problem","van bevern","fluschnik","tsidulko"],"title":"Parameterized algorithms and data reduction for the short secluded $s$-$t$-path problem","year":2020,"dataSources":["SMwzc9Bzq5Np5ikev","G5GefJqqu2DtnCZXz"]}