The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs
From MaRDI portal
Publication:1756342
Abstract: This work studies the parameterized complexity of finding secluded solutions to classical combinatorial optimization problems on graphs such as finding minimum s-t separators, feedback vertex sets, dominating sets, maximum independent sets, and vertex deletion problems for hereditary graph properties: Herein, one searches not only to minimize or maximize the size of the solution, but also to minimize the size of its neighborhood. This restriction has applications in secure routing and community detection.
Recommendations
Cites work
- A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
- A 4k^2 kernel for feedback vertex set
- A c^k n 5-approximation algorithm for treewidth
- A complexity dichotomy for finding disjoint solutions of vertex deletion problems
- A shortcut to (sun)flowers: kernels in logarithmic space or linear time
- Algorithms – ESA 2005
- An algorithmic framework for fixed-cardinality optimization in sparse graphs applied to dense subgraph problems
- An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints
- Approximation and tidying -- a problem kernel for s-plex cluster vertex deletion
- Cutting up is hard to do: the parameterised complexity of k-cut and related problems
- Finding good approximate vertex and edge partitions is NP-hard
- Finding highly connected subgraphs
- Finding secluded places of special interest in graphs
- Finding small separators in linear time via treewidth reduction
- Fixed-parameter algorithms for cluster vertex deletion
- Fixed-parameter tractability of graph modification problems for hereditary properties
- Fundamentals of parameterized complexity
- Graph theory
- Hardness of r-dominating set on graphs of diameter (r + 1)
- scientific article; zbMATH DE number 1261820 (Why is no real title available?)
- scientific article; zbMATH DE number 2234775 (Why is no real title available?)
- Isolation concepts for clique enumeration: comparison and computational experiments
- Isolation concepts for efficiently enumerating dense subgraphs
- Kernelization lower bounds through colors and IDs
- Network Analysis
- On the Parameterized Complexity of Cutting a Few Vertices from a Graph
- On the parameterized complexity of multiple-interval graph problems
- Parameterized algorithms
- Parameterized complexity of secluded connectivity problems
- Parameterized graph separation problems
- Parametrized complexity theory.
- Random Separation: A New Method for Solving Fixed-Cardinality Optimization Problems
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- The node-deletion problem for hereditary properties is NP-complete
- Towards optimal and expressive kernelization for \(d\)-hitting set
- Tree deletion set has a polynomial kernel but no \(\mathrm{OPT}^\mathcal{O}(1)\) approximation)
Cited in
(13)- Finding connected secluded subgraphs
- On the computational complexity of length- and neighborhood-constrained path problems
- Parameterized complexity of secluded connectivity problems
- Finding secluded places of special interest in graphs
- Finding connected secluded subgraphs
- Parameterized complexity of secluded connectivity problems
- 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
- On the complexity of secluded path problems
- A parameterized study of secluded structures in directed graphs
This page was built for publication: The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1756342)
