max planck institut
informatik

# MPI-INF or MPI-SWS or Local Campus Event Calendar

 << Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
Title: Erdos Posa Property in Digraphs Saeed Amiri Max-Planck-Institut für Informatik - D1 I did my Ph.D at TU-Berlin, my thesis focus was on connecting and covering problems in Graphs, in particular, I worked on Erdos Posa-property, dominating sets in the distributed model of computation, disjoint paths and flow rerouting problems. Currently, I'm a postdoc fellow at MPII. AG1 Mittagsseminar (own work) D1We use this to send out email in the morning. AG Audience English
Date: Tuesday, 9 January 2018 13:00 30 Minutes Saarbrücken E1 4 024
 In 1965 Erdos and Posa show that any graph either has many pairwise disjoint cycles or it has a small feedback vertex set. This is known as Erdos-Posa property. There still is room for generalization for Erdos and Posa property. Let H be a fixed graph, is there any relation between the number of disjoint minor models of H in any graph G and the size of a minimum set which hits all minor models of H in G? This natural generalization of the Erdos-Posa property was resolved by Robertson and Seymour who showed that the answer to above question is positive if and only if the graph H is planar. This, in fact, closed the mystery of the Erdos-Posa property in undirected graphs. A few years after Erdos and Posa’s great result (1973), Younger raised his famous conjecture for directed graphs: There is a function f : N → N such that for all k and all digraphs G = (V ; E), G contains k pairwise disjoint cycles or there is a set of vertices T ⊆ V such that G − T is acyclic and the size of T is bounded from above by f(k). Unlike undirected graphs, dealing with directed cycles was not easy and it took about a quarter of a century for researchers to answer Younger’s conjecture positively. As for undirected graphs one can consider the more general question for digraphs: Is there a function f : N → N such that for every digraph H and for all k and every digraphs G = (V ; E), G either has k disjoint butterfly models of H or there is a set of vertices T of size at most f(k + |H|) such that G − T has no butterfly model of H? We answer the above question if the graph H is strongly connected by providing a full classification. On the other hand we provide a characterization for vertex cyclic graphs (the class of graphs where every vertex lies on some cycle). We show that many natural graphs in that class do not have the Erdos and Posa property.
Name(s): Saeed Amiri samiri@mpi-in.mpg.de