Hitting Diamonds and Growing Cacti

Samuel Fiorini, Gwenaël Joret, Ugo Pietropaoli

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 c…