2016/03/08 by Saeed Akhoondian Amiri, Ken-Ichi Kawarabayashi, Amiri, Saeed Akhoondian +5
Computer Science · Mathematics · #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #cs.DM #math.CO
paper · pdf · doi:10.48550/arxiv.1603.02504
arxiv created 2016/03/14 · arxiv updated 2016/03/15
A classical result by Erdos and Posa states that there is a function f: \mathbb N → \mathbb N such that for every k, every graph G contains k pairwise vertex disjoint cycles or a set T of at most f(k) vertices such that G-T is acyclic. The generalisation of this result to directed graphs is known as Younger's conjecture and was proved by Reed, Robertson, Seymour and Thomas in 1996. This so-called Erdos-Posa-property can naturally be generalised to arbitrary graphs and digraphs. Robertson and Seymour proved that a graph H has the Erdos-Posa-property if, and only if, H is planar. In this paper we study the corresponding problem for digraphs. We obtain a complete characterisation of the class of strongly connected digraphs which have the Erdos-Posa-property (both for topological and butterfly minors). We also generalise this result to classes of digraphs which are not strongly connected. In particular, we study the class of vertex-cyclic digraphs (digraphs without trivial strong components). For this natural class of digraphs we obtain a nearly complete characterisation of the digraphs within this class with the Erdos-Posa-property. In particular we give positive and algorithmic examples of digraphs with the Erdos-Posa-property by using directed tree decompositions in a novel way.