Deciding the Erdős-Pósa property in 3-connected digraphs - IDEX UCA JEDI Université Côte d'Azur Access content directly
Conference Papers Year : 2023

Deciding the Erdős-Pósa property in 3-connected digraphs


A (di)graph H has the Erdős-Pósa (EP) property for (butterfly) minors if there exists a function f : N → N such that, for any k ∈ N and any (di)graph G, either G contains at least k pairwise vertexdisjoint copies of H as (butterfly) minor, or there exists a subset T of at most f (k) vertices such that H is not a (butterfly) minor of G − T. It is a well known result of Robertson and Seymour that an undirected graph has the EP property if and only if it is planar. This result was transposed to digraphs by Amiri, Kawarabayashi, Kreutzer and Wollan, who proved that a strong digraph has the EP property for butterfly minors if, and only if, it is a butterfly minor of a cylindrical grid. Contrary to the undirected case where a graph is planar if, and only if, it is the minor of some grid, not all planar digraphs are butterfly minors of a cylindrical grid. In this work, we characterize the planar digraphs that have a butterfly model in a cylindrical grid. In particular, this leads to a linear-time algorithm that decides whether a weakly 3-connected strong digraph has the EP property.
Fichier principal
Vignette du fichier
Directed_Cylindrical_Grid_and_Models___New_version-6.pdf (513.46 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

hal-04084227 , version 1 (27-04-2023)



  • HAL Id : hal-04084227 , version 1


Julien Bensmail, Victor Campos, Ana Karolinna Maia, Nicolas Nisse, Ana Silva. Deciding the Erdős-Pósa property in 3-connected digraphs. WG 2023 - 49th International Workshop on Graph-Theoretic Concepts in Computer Science, Jun 2023, Fribourg (CH), Switzerland. ⟨hal-04084227⟩
39 View
73 Download


Gmail Mastodon Facebook X LinkedIn More