- Title: “Subdivisions of Digraphs”
- When: November 5, 2014 — 10:00
- Where: Room Euler Violet, Inria Sophia Antipolis – Méditerranée
- Stéphane Bessy (Referee), LIRMM Montpellier, France
- Frédéric Havet (Supervisor), COATI, Inria/I3S-UNS, France
- Frédéric Maffray, Laboratoire G-SCOP, Grenoble, France
- Adrien Richard, I3S (CNRS/UNS), Sophia Antipolis, France
- Nicolas Trotignon (Referee), ENS Lyon, France
- Yann Vaxès, LIF, UFR Sciences Luminy, France
Abstract: In this work, we consider the following problem: Given a directed graph D, does it contain a subdivision of a prescribed digraph F? We believe that there is a dichotomy between NP-complete and polynomial-time solvable instances of this problem. We present many examples of both cases. In particular, except for five instances, we are able to classify all the digraphs F of order 4. While all NP-hardness proofs are made by reduction from some version of the 2-linkage problem in digraphs, we use different algorithmic tools for proving polynomial-time solvability of certain instances, some of them involving relatively complicated algorithms. The techniques vary from easy brute force algorithms, algorithms based on maximum-flow calculations, handle decompositions of strongly connected digraphs, among others.
Finally, we treat the very special case of F being the disjoint union of directed cycles. In particular, we show that the directed cycles of length at least 3 have the Erdos-Pósa Property: for every n, there exists an integer tn 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 tn vertices that meets every directed cycle of length at least 3. From this result, 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.
Keywords: Digraphs, subdivisions.