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

Journal Article

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.

Related Topics

Related Publications

Related Content

Site Footer


This website is provided by John Wiley & Sons Limited, The Atrium, Southern Gate, Chichester, West Sussex PO19 8SQ (Company No: 00641132, VAT No: 376766987)

Published features on are checked for statistical accuracy by a panel from the European Network for Business and Industrial Statistics (ENBIS)   to whom Wiley and express their gratitude. This panel are: Ron Kenett, David Steinberg, Shirley Coleman, Irena Ograjenšek, Fabrizio Ruggeri, Rainer Göb, Philippe Castagliola, Xavier Tort-Martorell, Bart De Ketelaere, Antonio Pievatolo, Martina Vandebroek, Lance Mitchell, Gilbert Saporta, Helmut Waldl and Stelios Psarakis.