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
Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués, CRISAM - Inria Sophia Antipolis - Méditerranée
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.
Complete list of metadatas

Cited literature [9 references]  Display  Hide  Download

https://hal.inria.fr/hal-00816135
Contributor : Ana Karolinna Maia de Oliveira <>
Submitted on : Saturday, April 20, 2013 - 10:23:36 PM
Last modification on : Monday, November 5, 2018 - 3:36:03 PM
Long-term archiving on : Monday, April 3, 2017 - 11:21:37 PM

File

RR-8286.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00816135, version 2

Collections

Citation

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

Share

Metrics

Record views

739

Files downloads

229