Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

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)
What and Who
Title:Erdos Posa Property in Digraphs
Speaker:Saeed Amiri
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio: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.
Event Type:AG1 Mittagsseminar (own work)
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Tuesday, 9 January 2018
Duration:30 Minutes
Building:E1 4
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
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Keywords:erdos posa property; digraphs; structural graph properties
Note:This will be a very elementary talk on the topic, we just explain the problem statement and few ideas. It does not need any prerequisites and we are not going to any technical detail.

However, if anyone is interested in the topic, I suggest the following papers to take a look at it:
1. Last section of Graph Minor V:
2. P. Erdos and L. Pósa. On independent circuits contained in a graph. ˝ Canadian Journal of Mathematics, 1965.
The latter has not been updated for a while, I could hand in my thesis which includes this papaer in more details and it is more accurate, so if you want please don't hesitate and just email me.
Attachments, File(s):

Saeed Amiri, 01/05/2018 01:07 PM
Last modified:
Uwe Brahm/MPII/DE, 01/09/2018 04:01 AM
  • Saeed Amiri, 01/05/2018 01:20 PM
  • Saeed Amiri, 01/05/2018 01:07 PM -- Created document.