Parameterized Complexity of Secluded Connectivity Problems
Parameterized Complexity of Secluded Connectivity Problems
复制标题
隐蔽连接问题的参数化复杂性
DOI：
10.1007/s00224-016-9717-x
复制
发表时间：
2015
影响因子：
0.5
通讯作者：
A. Kulikov
中科院分区：
文献类型：
--
作者：
F. Fomin;P. Golovach;Nikolai Karpov;A. Kulikov
僻静的路径问题模型必须在网络中的路径上传输敏感信息。邻居。在本文中最小化。在顶点之间。我们还展示了如何扩展僻静的施泰纳树的结果，在这种情况下，我们将最佳施泰纳树的大小和终端的数量进行参数化。顶点覆盖物的大小，反馈顶点集或问题的最大顶点度和建立核心化的复杂性，但要承担不同的参数选择。
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, i.e., 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 parameters.