The induced-subdivision dichotomy conjecture for digraphs
The induced-subdivision dichotomy conjecture for digraphs
Let be a digraph. For a digraph , let denote the problem of deciding whether contains an induced subdivision of . A spider is a tree obtained from disjoint directed paths by identifying one end of each path into a vertex, and is the digraph on two vertices with both possible arcs.
Induced-subdivision dichotomy conjecture. is NP-complete unless is the disjoint union of spiders and at most one -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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.