The induced-subdivision dichotomy conjecture for digraphs

Let DD be a digraph. For a digraph GG, let iDi_D denote the problem of deciding whether GG contains an induced subdivision of DD. A spider is a tree obtained from disjoint directed paths by identifying one end of each path into a vertex, and C2C_2 is the digraph on two vertices with both possible arcs.

Induced-subdivision dichotomy conjecture. iDi_D is NP-complete unless DD is the disjoint union of spiders and at most one 22-cycle.

This conjecture proposes the complexity dichotomy for induced-subdivision detection in digraphs; the preceding results establish the analogous statement for oriented graphs, while the general digraph case remains open.

Sources & referencesView supporting material

Primary source

Jørgen Bang-Jensen, Frédéric Havet and Nicolas Trotignon, “Finding an induced subdivision of a digraph”, arXiv:1309.1553 (2013).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.