Campus Event Calendar
Event Entry
What and Who
Erdos Posa Property in Digraphs
Saeed Amiri
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
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.
AG 1
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Tuesday, 9 January 2018
13:00
30 Minutes
E1 4
024
Saarbrücken
Abstract
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.
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.
Contact
Saeed Amiri
--email hidden
passcode not visible
logged in users only
Tags, Category, Keywords and additional notes
erdos posa property; digraphs; structural graph properties
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: http://www.sciencedirect.com/science/article/pii/0095895686900304
2. P. Erdos and L. Pósa. On independent circuits contained in a graph. ˝ Canadian Journal of Mathematics, 1965.
3. https://arxiv.org/abs/1603.02504
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.
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: http://www.sciencedirect.com/science/article/pii/0095895686900304
2. P. Erdos and L. Pósa. On independent circuits contained in a graph. ˝ Canadian Journal of Mathematics, 1965.
3. https://arxiv.org/abs/1603.02504
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.
Saeed Amiri, 01/05/2018 13:20
Saeed Amiri, 01/05/2018 13:07 -- Created document.
Saeed Amiri, 01/05/2018 13:07 -- Created document.