Monotonicity conjecture for induced-subdivision detection
Monotonicity conjecture for induced-subdivision detection
Let and be digraphs. For a digraph , let (respectively, ) denote the corresponding induced-subdivision detection problem. Say that is an induced subdigraph of if contains a vertex-induced copy of .
Monotonicity conjecture. If (respectively, ) is NP-complete, then for every digraph containing as an induced subdigraph, (respectively, ) 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
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.