TY - GEN

T1 - Parameterized complexity of secluded connectivity problems

AU - Fomin, Fedor V.

AU - Golovach, Petr A.

AU - Karpov, Nikolay

AU - Kulikov, Alexander S.

PY - 2015/12/1

Y1 - 2015/12/1

N2 - The Secluded Path problem introduced by Chechik et al. in [ESA 2013] models a situation where a 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, which is the total weight of vertices in its closed neighborhood. In order to minimize the risk of intercepting the information, we are interested in selecting a secluded path, i.e. a path with a small exposure. Similarly, the Secluded Steiner Tree problem is to find a tree in a graph connecting a given set of terminals such that the exposure of the tree is minimized. In this work, we obtain the following results about parameterized complexity of secluded connectivity problems. We start from an observation that being parameterized by the size of the exposure, the problem is fixed-parameter tractable (FPT). More precisely, we give an algorithm deciding if a graph G with a given cost function ω: V (G) → ℕ contains a secluded path of exposure at most k with the cost at most C in time O(3k/3 · (n+m) logW), where W is the maximum value of ω on an input graph G. Similarly, Secluded Steiner Tree is solvable in time O(2kk2 · (n+m) logW). The main result of this paper is about "above guarantee" parameterizations for secluded problems. We show that Secluded Steiner Tree is FPT being parameterized by r+p, where p is the number of the terminals, ℓ the size of an optimum Steiner tree, and r = k - ℓ. We complement this result by showing that the problem is co-W[1]-hard when parameterized by r only. We also investigate Secluded Steiner Tree from kernelization perspective and provide several lower and upper bounds when parameters are the treewidth, the size of a vertex cover, maximum vertex degree and the solution size. Finally, we refine the algorithmic result of Chechik et al. by improving the exponential dependence from the treewidth of the input graph.

AB - The Secluded Path problem introduced by Chechik et al. in [ESA 2013] models a situation where a 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, which is the total weight of vertices in its closed neighborhood. In order to minimize the risk of intercepting the information, we are interested in selecting a secluded path, i.e. a path with a small exposure. Similarly, the Secluded Steiner Tree problem is to find a tree in a graph connecting a given set of terminals such that the exposure of the tree is minimized. In this work, we obtain the following results about parameterized complexity of secluded connectivity problems. We start from an observation that being parameterized by the size of the exposure, the problem is fixed-parameter tractable (FPT). More precisely, we give an algorithm deciding if a graph G with a given cost function ω: V (G) → ℕ contains a secluded path of exposure at most k with the cost at most C in time O(3k/3 · (n+m) logW), where W is the maximum value of ω on an input graph G. Similarly, Secluded Steiner Tree is solvable in time O(2kk2 · (n+m) logW). The main result of this paper is about "above guarantee" parameterizations for secluded problems. We show that Secluded Steiner Tree is FPT being parameterized by r+p, where p is the number of the terminals, ℓ the size of an optimum Steiner tree, and r = k - ℓ. We complement this result by showing that the problem is co-W[1]-hard when parameterized by r only. We also investigate Secluded Steiner Tree from kernelization perspective and provide several lower and upper bounds when parameters are the treewidth, the size of a vertex cover, maximum vertex degree and the solution size. Finally, we refine the algorithmic result of Chechik et al. by improving the exponential dependence from the treewidth of the input graph.

KW - Parameterized complexity

KW - Secluded path

KW - Secluded Steiner tree

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

U2 - 10.4230/LIPIcs.FSTTCS.2015.408

DO - 10.4230/LIPIcs.FSTTCS.2015.408

M3 - Conference contribution

AN - SCOPUS:84958756143

T3 - Leibniz International Proceedings in Informatics, LIPIcs

SP - 408

EP - 419

BT - 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2015

A2 - Harsha, Prahladh

A2 - Ramalingam, G.

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2015

Y2 - 16 December 2015 through 18 December 2015

ER -