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

{"_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://bibbase.org/show?bib=http%3A%2F%2Frvb.su%2Frvb.bib&commas=true"}}},"bibtype":"article","biburl":"http://rvb.su/rvb.bib","creationDate":"2021-01-06T14:24:56.572Z","downloads":0,"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"]}