A tight approximation algorithm for the cluster vertex deletion problem

DOI10.1007/978-3-030-73879-2_24MaRDI QIDQ5918432zbMATH OpenOpenAlexFDO

Authors Manuel Aprile, Matthew Drescher, Samuel Fiorini, Tony Huynh

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 algorithmcluster vertex deletionlinear programming relaxationSherali-Adams hierarchy

Mathematics Subject Classification ID

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

Abstract: We give the first $2$-approximation algorithm for the cluster vertex deletion problem. This is tight, since approximating the problem within any constant factor smaller than $2$ is UGC-hard. Our algorithm combines the previous approaches, based on the local ratio technique and the management of true twins, with a novel construction of a 'good' cost function on the vertices at distance at most $2$ from any vertex of the input graph. As an additional contribution, we also study cluster vertex deletion from the polyhedral perspective, where we prove almost matching upper and lower bounds on how well linear programming relaxations can approximate the problem.

Recommendations

• A tight approximation algorithm for the cluster vertex deletion problem
• Faster parameterized algorithm for cluster vertex deletion
• A fast branching algorithm for cluster vertex deletion
• A fast branching algorithm for cluster vertex deletion

Cites work

• 2-Approximating Feedback Vertex Set in Tournaments
• A 7/3-approximation for feedback vertex sets in tournaments
• A fast branching algorithm for cluster vertex deletion
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• A tight approximation algorithm for the cluster vertex deletion problem
• An approximation algorithm for feedback vertex sets in tournaments
• Analysis of complex network performance and heuristic node removal strategies
• Decomposition by clique separators
• Faster parameterized algorithm for pumpkin vertex deletion set
• Fixed-parameter algorithms for cluster vertex deletion
• Graph fragmentation problem: analysis and synthesis
• scientific article; zbMATH DE number 554762 (Why is no real title available?)
• No small linear program approximates vertex cover within a factor \(2 -\varepsilon\)
• Polyhedral properties of the induced cluster subgraphs
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Subquadratic kernels for implicit 3-{\textsc{Hitting Set}} and 3-{\textsc{Set Packing}} problems

Cited in

(9)

• Faster parameterized algorithm for cluster vertex deletion
• A 2-approximation for the bounded treewidth sparsest cut problem in \textsf{FPT} Time
• On the d-claw vertex deletion problem
• Kernelization through Tidying
• A tight approximation algorithm for the cluster vertex deletion problem
• A tight approximation algorithm for the cluster vertex deletion problem
• 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
• On the parameterized complexity of s-club cluster deletion problems

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5918432)