Hitting diamonds and growing cacti

DOI10.1007/978-3-642-13036-6_15MaRDI QIDQ3569818zbMATH OpenOpenAlexFDO

Authors Samuel Fiorini, Gwenaël Joret, Ugo Pietropaoli

Publication date 22 June 2010

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

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

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Integer programming (90C10)

Abstract: We consider the following NP-hard problem: in a weighted graph, find a minimum cost set of vertices whose removal leaves a graph in which no two cycles share an edge. We obtain a constant-factor approximation algorithm, based on the primal-dual method. Moreover, we show that the integrality gap of the natural LP relaxation of the problem is Theta(log n), where n denotes the number of vertices in the graph.

Recommendations

• Publication:4886063
• An approximation algorithm for minimum-cost vertex-connectivity problems
• Multiway cuts in node weighted graphs
• Capacitated vertex covering
• On cutting a few vertices from a graph

Cited in

(11)

• A constant-factor approximation for weighted bond cover
• Hitting forbidden minors: approximation and kernelization
• Polylogarithmic approximation algorithms for weighted-\(\mathcal{F}\)-deletion problems
• An improved deterministic parameterized algorithm for cactus vertex deletion
• Hitting weighted even cycles in planar graphs
• scientific article; zbMATH DE number 7765420 (Why is no real title available?)
• Small minors in dense graphs
• scientific article; zbMATH DE number 6784975 (Why is no real title available?)
• Quick but odd growth of cacti
• An \(O(\log \mathrm{OPT})\)-approximation for covering and packing minor models of \(\theta _r\)
• Towards constant-factor approximation for chordal/distance-hereditary vertex deletion

This page was built for publication: Hitting diamonds and growing cacti

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