A tight approximation algorithm for the cluster vertex deletion problem
From MaRDI portal
Publication:5925651
DOI10.1007/s10107-021-01744-wMaRDI QIDQ5925651
Matthew Drescher, Samuel Fiorini, Tony Huynh, Manuel Aprile
Publication date: 14 March 2023
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10107-021-01744-w
approximation algorithm; linear programming relaxation; cluster vertex deletion; Sherali-Adams hierarchy
90Cxx: Mathematical programming
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A fast branching algorithm for cluster vertex deletion
- Analysis of complex network performance and heuristic node removal strategies
- Approximate association via dissociation
- Fixed-parameter algorithms for cluster vertex deletion
- Decomposition by clique separators
- Extension complexity of stable set polytopes of bipartite graphs
- Vertex deletion problems on chordal graphs
- Strong reductions for extended formulations
- Polyhedral properties of the induced cluster subgraphs
- Improved approximation algorithms for hitting 3-vertex paths
- Extended formulations for matroid polytopes through randomized protocols
- An Approximation Algorithm for Feedback Vertex Sets in Tournaments
- Inapproximability of Combinatorial Problems via Small LPs and SDPs
- Approximate Constraint Satisfaction Requires Large LP Relaxations
- Integer Programming
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- A 7/3-Approximation for Feedback Vertex Sets in Tournaments
- Subquadratic Kernels for Implicit 3-H <scp>itting</scp> S <scp>et</scp> and 3-S <scp>et</scp> P <scp>acking</scp> Problems
- Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs
- 2-Approximating Feedback Vertex Set in Tournaments
- No Small Linear Program Approximates Vertex Cover Within a Factor 2 − ɛ
- Exact Algorithms via Monotone Local Search
- A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
- A tight approximation algorithm for the cluster vertex deletion problem
- Extended formulations from communication protocols in output-efficient time
- Graph fragmentation problem: analysis and synthesis
