Seminar

Speaker:	Δημήτριος Μ. Θηλυκός (Καθηγητής, Τμήμα μαθηματικών ΕΚΠΑ, ΕΚΠΑ)
Title:	Optimal Erdős-Pósa proterties for θ_r minor models
Date:	Παρασκευή, 28 Φεβ 2014
Ώρα:	18:30-19:30
Location:	Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών, Τμήμα Μαθηματικών, room Γ33

Abstract

Typically, Erdős–Pósa properties reveal relations between covering and packing invariants in combinatorial structures. The origin of the study of such properties comes from the celebrated Erdős–Pósa Theorem (1695), stating that there is a function f : N → N such that for every k ∈ N and for every graph G, either G contains k vertex-disjoint cycles or there is a set X of f(k) vertices in G meeting all cycles of G. In particular, Erdős and Pósaa proved this result for f(k) = O(k · log k) and showed that this bound is optimal. Given a graph J, we denote by M(J) the set of all graphs that can be contracted to J (also called models of J). Robertson and Seymour proved that the class M(J) satisfies the Erdős–Pósa property if and only if J is planar. Notice that this can be seen as the (qualitatively tight) extension of the Erdős–Pósa Theorem (take J = θ2 where, in general, θr is the graph consisting of two vertices and r parallel edges between them). The emerging question is whether (and when) the function involved in the above proposition can match the (optimal) O(k log k) bound of Erdős–Pósa and whether this bound can be improved under several assumptions on the considered graphs. Given two graphs H and G, we denote by packH (G) as the maximum number of vertex-disjoint models of H in G. We also denote by cover_H (G) the minimum number of vertices that intersect all models of H in G. We prove the following result. Theorem 1. There exist a function f : N → N such that for every two positive integers r, q and every graph G excluding K_q as a minor, it holds that cover_θ_r (G) ≤ f (r) · pack_θ_r (G) · log q. Our proof can be adapted for the edge-variant of the same theorem (where we consider edge coverings and edge-disjoint models). Our results also imply that, for every r, the problems of computing the values of pack_θ_r , coverv_θ_r , as well as their “edge” counterparts admit log(OPT)-approximation (deterministic and polynomial) algorithms. This improves existing results on the approximability of the above graph invariants. (Joint work with: Dimitris Chatzidimitriou, Jean-Florent Raymond, and Ignasi Sau).