Monotonicity conjecture for induced-subdivision detection

Let DD and DD' be digraphs. For a digraph GG, let iDi_D (respectively, iDi'_D) denote the corresponding induced-subdivision detection problem. Say that DD is an induced subdigraph of DD' if DD' contains a vertex-induced copy of DD.

Monotonicity conjecture. If iDi_D (respectively, iDi'_D) is NP-complete, then for every digraph DD' containing DD as an induced subdigraph, iDi_{D'} (respectively, iDi'_{D'}) is NP-complete.

The conjecture is proposed as a tool for proving a full complexity dichotomy. It covers both variants discussed in the paper and is open according to the surrounding remarks.

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.