Name
Abstract | ||
|---|---|---|
Given a graph G = (V, E), two vertices s, t is an element of V, and two integers k, l, the Short Secluded Path problem is to find a simple s-t-path with at most k vertices and l 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 l. We also obtain a 2(O(tw)) center dot l(2) center dot n-time algorithm for n-vertex graphs of treewidth tw, which yields subexponential-time algorithms in several graph classes. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.1002/net.21904 | NETWORKS |
Keywords | Field | DocType |
fixed-parameter tractability,kernelization lower bounds,NP-hard problem,problem kernelization,subexponential time,treewidth | Combinatorics,Treewidth,Mathematics,Data reduction,Parameterized algorithms | Journal |
Volume | Issue | ISSN |
75.0 | 1.0 | 0028-3045 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| René van Bevern | 1 | 126 | 19.33 |
| till fluschnik | 2 | 11 | 1.92 |
| O. Yu. Tsidulko | 3 | 1 | 2.85 |