A tight approximation algorithm for the cluster vertex deletion problem

DOI10.1007/978-3-030-73879-2_24zbMath1482.90176arXiv2007.08057OpenAlexW3162862852MaRDI QIDQ5918432

Matthew Drescher, Manuel Aprile, Tony Huynh, Samuel Fiorini

Publication date: 21 December 2021

Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2007.08057

zbMATH Keywords

approximation algorithmlinear programming relaxationcluster vertex deletionSherali-Adams hierarchy

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items (5)

A 2-approximation for the bounded treewidth sparsest cut problem in \textsf{FPT} Time ⋮ \(s\)-club cluster vertex deletion on interval and well-partitioned chordal graphs ⋮ A \(7 / 3\)-approximation algorithm for feedback vertex set in tournaments via Sherali-Adams ⋮ A tight approximation algorithm for the cluster vertex deletion problem ⋮ A tight approximation algorithm for the cluster vertex deletion problem

Cites Work

• 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
• Polyhedral properties of the induced cluster subgraphs
• Improved approximation algorithms for hitting 3-vertex paths
• Faster parameterized algorithm for pumpkin vertex deletion set
• An Approximation Algorithm for Feedback Vertex Sets in Tournaments
• 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
• 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 tight approximation algorithm for the cluster vertex deletion problem
• Graph fragmentation problem: analysis and synthesis

This page was built for publication: A tight approximation algorithm for the cluster vertex deletion problem