Finding an induced subdivision of a digraph.

Jørgen Bang-Jensen (1) , Frédéric Havet (2) , Nicolas Trotignon (3)

1 IMADA - Department of Mathematics and Computer Science [Odense]
2 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
3 LIAFA - Laboratoire d'informatique Algorithmique : Fondements et Applications

We consider the following problem for oriented graphs and digraphs: Given an oriented graph (digraph) G, does it contain an induced subdivision of a prescribed digraph D? The complexity of this problem depends on D and on whether G must be an oriented graph or is allowed to contain 2-cycles. We give a number of examples of polynomial instances as well as several NP-completeness proofs.

Domaines: Mathématique discrète [cs.DM]

Jørgen Bang-Jensen, Frédéric Havet, Nicolas Trotignon. Finding an induced subdivision of a digraph.. Theoretical Computer Science, 2012, 443, pp.10--24. ⟨hal-00749187⟩