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

Standard

Parameterized algorithms and data reduction for the short secluded s-t-path problem. / van Bevern, René; Fluschnik, Till; Tsidulko, Oxana Yu.

In: Networks, Vol. 75, No. 1, 01.2020, p. 34-63.

Research output: Contribution to journal › Article › peer-review

BibTeX

@article{6c305fcf9ae44eaabba529c14fe6623a,

title = "Parameterized algorithms and data reduction for the short secluded s-t-path problem",

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

keywords = "fixed-parameter tractability, kernelization lower bounds, NP-hard problem, problem kernelization, subexponential time, treewidth, EULERIAN EXTENSION, APPROXIMATION, COMPLEXITY",

author = "{van Bevern}, Ren{\'e} and Till Fluschnik and Tsidulko, {Oxana Yu}",

year = "2020",

month = jan,

doi = "10.1002/net.21904",

language = "English",

volume = "75",

pages = "34--63",

journal = "Networks",

issn = "0028-3045",

publisher = "Wiley-Liss Inc.",

number = "1",

}

RIS

TY - JOUR

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

AU - van Bevern, René

AU - Fluschnik, Till

AU - Tsidulko, Oxana Yu

PY - 2020/1

Y1 - 2020/1

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

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

KW - fixed-parameter tractability

KW - kernelization lower bounds

KW - NP-hard problem

KW - problem kernelization

KW - subexponential time

KW - treewidth

KW - EULERIAN EXTENSION

KW - APPROXIMATION

KW - COMPLEXITY

UR - http://www.scopus.com/inward/record.url?scp=85071289401&partnerID=8YFLogxK

U2 - 10.1002/net.21904

DO - 10.1002/net.21904

M3 - Article

AN - SCOPUS:85071289401

VL - 75

SP - 34

EP - 63

JO - Networks

JF - Networks

SN - 0028-3045

IS - 1

ER -

ID: 21344933