PhD defense of Ana Karolinna Maia de Oliveira

PhD Ana Karolinna Maia de Oliveira

  • Title: “Subdivisions of Digraphs”
  • When: November 5, 2014 — 10:00
  • Where: Room Euler Violet, Inria Sophia Antipolis – Méditerranée
  • Committee:
  • 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.

Comments are closed