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

Julien Bensmail (1) , Victor Campos (2) , Ana Karolinna Maia (2) , Nicolas Nisse (1) , Ana Silva (2)

1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
2 ParGO - Parallelism, Graphs and Optimization Research Group

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.

Mots clés: Erdős-Pósa property; Planar digraphs; Butterfly minor

Domaines: Informatique [cs]

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⟩