Monotonicity conjecture for induced-subdivision detection
Statement
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.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.