The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs
From MaRDI portal
Publication:1756342
DOI10.1016/j.disopt.2018.05.002zbMath1454.90104arXiv1606.09000OpenAlexW2886236358WikidataQ129365416 ScholiaQ129365416MaRDI QIDQ1756342
Manuel Sorge, Hendrik Molter, George B. Mertzios, Ondřej Suchý, Till Fluschnik, René van Bevern
Publication date: 14 January 2019
Published in: Discrete Optimization (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1606.09000
Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Finding connected secluded subgraphs ⋮ Finding \(k\)-secluded trees faster ⋮ Parameterized algorithms and data reduction for the short secluded s‐t‐path problem ⋮ Finding \(k\)-secluded trees faster ⋮ On the computational complexity of length- and neighborhood-constrained path problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- Towards optimal and expressive kernelization for \(d\)-hitting set
- Parameterized graph separation problems
- Isolation concepts for efficiently enumerating dense subgraphs
- Fixed-parameter algorithms for cluster vertex deletion
- On the parameterized complexity of multiple-interval graph problems
- Isolation concepts for clique enumeration: comparison and computational experiments
- The node-deletion problem for hereditary properties is NP-complete
- Finding good approximate vertex and edge partitions is NP-hard
- Fixed-parameter tractability of graph modification problems for hereditary properties
- Secluded connectivity problems
- An algorithmic framework for fixed-cardinality optimization in sparse graphs applied to dense subgraph problems
- Parameterized complexity of secluded connectivity problems
- Approximation and tidying -- a problem kernel for \(s\)-plex cluster vertex deletion
- Parametrized complexity theory.
- An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- A $c^k n$ 5-Approximation Algorithm for Treewidth
- On the Parameterized Complexity of Cutting a Few Vertices from a Graph
- Hardness of r-dominating set on Graphs of Diameter (r + 1)
- A 4 k 2 kernel for feedback vertex set
- Finding small separators in linear time via treewidth reduction
- A Shortcut to (Sun)Flowers: Kernels in Logarithmic Space or Linear Time
- Random Separation: A New Method for Solving Fixed-Cardinality Optimization Problems
- A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
- Kernelization Lower Bounds Through Colors and IDs
- Finding Highly Connected Subgraphs
- Algorithms – ESA 2005
- Parameterized Algorithms
- Network Analysis
- Tree Deletion Set Has a Polynomial Kernel but No $\text{OPT}^\mathcal{O}(1)$ Approximation)
- A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems
