Séminaire

Pas de visio-conférence A class of graphs F has the Erdos-Posa property if the cardinalities of a covering and a packing of F satisfy a loose min-max relation in any graph. A simple example is the Erdos-Posa theorem, which state that the class of cycles has this property : every graph contains k vertex-disjoint cycles, or has O(k log k) vertices covering every cycle, for every positive integer k. There are two variants of the Erdos-Posa property : one where packings must be vertex-disjoint and where a cover is a set of vertices, and the edge-version defined similarly by replacing every occurrence of 'vertex' by 'edge'. In this talk, I will show how this purely combinatorial property can be used in the design of approximation algorithms. More precisely, I will consider the class of graphs which contract to the multiedge ofmultiplicity r, and show that the problems of maximum packing and minimum covering of graphs from this class admit a O(log OPT)-approximation algorithm. This result holds for both the vertex and edge version and improves the previous O(log n)-approximation of Joret et al., 2011 for the vertex version. The proof relies on a protrusion-based reduction and on a combinatorial lemma stating that a reduced graph contains a large packing. This is joint work with Dimitris Chatzidimitriou (University of Athens), Ignasi Sau (LIRMM CNRS) and Dimitrios Thilikos (LIRMM CNRS and University of Athens).