Parameterized complexity of secluded connectivity problems
From MaRDI portal
Abstract: The Secluded Path problem 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. The problems were introduced by Chechik et al. in [ESA 2013]. Among other results, Chechik et al. have shown that Secluded Path is fixed-parameter tractable (FPT) on unweighted graphs being parameterized by the maximum vertex degree of the graph and that Secluded Steiner Tree is FPT parameterized by the treewidth of the graph. In this work, we obtain the following results about parameterized complexity of secluded connectivity problems. We give FPT-algorithms deciding if a graph G with a given cost function contains a secluded path and a secluded Steiner tree of exposure at most k with the cost at most C. We initiate the study of "above guarantee" parameterizations for secluded problems, where the lower bound is given by the size of a Steiner tree. We 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.
Recommendations
Cites work
- A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
- Color-coding
- Exact exponential algorithms.
- Fast polynomial-space algorithms using inclusion-exclusion. Improving on Steiner tree and related problems
- Fourier meets M\"{o}bius: fast subset convolution
- Fundamentals of parameterized complexity
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1261820 (Why is no real title available?)
- Kernelization Lower Bounds by Cross-Composition
- Kernels for below-upper-bound parameterizations of the hitting set and directed dominating set problems
- On problems without polynomial kernels
- On the parameterized complexity of multiple-interval graph problems
- On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
- Optimization of Pearl's method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem
- Parameterized algorithms
- Parameterized complexity of secluded connectivity problems
- Random Separation: A New Method for Solving Fixed-Cardinality Optimization Problems
- Reducibility among combinatorial problems
- Secluded path via shortest path
- The steiner problem in graphs
- Treewidth computation and extremal combinatorics
- VC-dimension of perimeter visibility domains
Cited in
(15)- The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs
- Finding connected secluded subgraphs
- On the computational complexity of length- and neighborhood-constrained path problems
- On the complexity landscape of connected \(f\)-factor problems
- Finding secluded places of special interest in graphs
- Finding connected secluded subgraphs
- Parameterized complexity of secluded connectivity problems
- Secluded path via shortest path
- Parameterized algorithms for finding highly connected solution
- Parameterized algorithms for finding highly connected solution
- Finding k-secluded trees faster
- Parameterized algorithms and data reduction for the short secluded s‐t‐path problem
- Finding \(k\)-secluded trees faster
- Single-exponential FPT algorithms for enumerating secluded \(\mathcal{F}\)-free subgraphs and deleting to scattered graph classes
- Single-exponential FPT algorithms for enumerating secluded \(\mathcal{F}\)-free subgraphs and deleting to scattered graph classes
This page was built for publication: Parameterized complexity of secluded connectivity problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2408560)
