Parameterized Complexity of Secluded Connectivity

Authors: Fedor V Fomin Petr A Golovach Nikolay Karpov Alexander S Kulikov

Publish Date: 2016/11/10

Volume: 61, Issue: 3, Pages: 795-819

PDF Link

Abstract

The Secluded Path problem models a situation where sensitive information has to be transmitted between a pair of nodes along a path in a network The measure of the quality of a selected path is its exposure cost which is the total cost of vertices in its closed neighborhood The task is to select a secluded path ie a path with a small exposure cost Similarly the Secluded Steiner Tree problem is to find a tree in a graph connecting a given set of terminals such that the exposure cost of the tree is minimized In this paper we present a systematic study of the parameterized complexity of Secluded Steiner Tree In particular we establish the tractability of Secluded Path being parameterized by “above guarantee” value which in this case is the length of a shortest path between vertices We also show how to extend this result for Secluded Steiner Tree in this case we parameterize above the size of an optimal Steiner tree and the number of terminals We also consider various parameterization of the problems such as by the treewidth the size of a vertex cover feedback vertex set or the maximum vertex degree and establish kernelization complexity of the problem subject to different choices of parametersA preliminary version of this paper appeared as an extended abstract in the proceedings of FSTTCS 2015 15 The research leading to these results has received funding from the European Research Council under the European Union’s Seventh Framework Programme FP/20072013 / ERC Grant Agreement n 267959 and the Government of the Russian Federation grant 14Z50310030

Keywords: