Monotonicity conjecture for induced-subdivision detection

About 13 years old · traced to

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

Monotonicity conjecture. If iDi_D (respectively, iD′i'_D) is NP-complete, then for every digraph D′D' containing DD as an induced subdigraph, iD′i_{D'} (respectively, iD′′i'_{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.

References

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.