Hitting diamonds and growing cacti
From MaRDI portal
Publication:3569818
DOI10.1007/978-3-642-13036-6_15zbMATH Open1284.05282arXiv0911.4366OpenAlexW1591716186MaRDI QIDQ3569818FDOQ3569818
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)
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.
Full work available at URL: https://arxiv.org/abs/0911.4366
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Integer programming (90C10)
Cited In (12)
- Title not available (Why is that?)
- Quick but odd growth of cacti
- Hitting weighted even cycles in planar graphs
- An \(O(\log \mathrm{OPT})\)-approximation for covering and packing minor models of \(\theta _r\)
- Hitting and Harvesting Pumpkins
- Polylogarithmic approximation algorithms for weighted-\(\mathcal{F}\)-deletion problems
- Towards constant-factor approximation for chordal/distance-hereditary vertex deletion
- Small minors in dense graphs
- Title not available (Why is that?)
- A constant-factor approximation for weighted bond cover
- Hitting forbidden minors: approximation and kernelization
- An improved deterministic parameterized algorithm for cactus 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)
