On disjoint directed cycles with prescribed minimum lengths

Frédéric Havet 1 Ana Karolinna Maia 1
1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : In this paper, we show that the k-Linkage problem is polynomial-time solvable for digraphs with circumference at most 2. We also show that the directed cycles of length at least 3 have the Erdős-Pósa Property : for every n, there exists an integer t_n such that for every digraph D, either D contains n disjoint directed cycles of length at least 3, or there is a set T of t_n vertices that meets every directed cycle of length at least 3. From these two results, we deduce that if F is the disjoint union of directed cycles of length at most 3, then one can decide in polynomial time if a digraph contains a subdivision of F.
Type de document :
[Research Report] RR-8286, INRIA. 2013

Contributeur : Ana Karolinna Maia de Oliveira <>
Soumis le : samedi 20 avril 2013 - 22:23:36
Dernière modification le : samedi 17 septembre 2016 - 01:36:46


Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-00816135, version 2



Frédéric Havet, Ana Karolinna Maia. On disjoint directed cycles with prescribed minimum lengths. [Research Report] RR-8286, INRIA. 2013. <hal-00816135v2>



Consultations de
la notice


Téléchargements du document