Strong Dichotomy Conjecture for graph covers
Statement
For every graph , consider the problem of deciding whether an input graph covers . Strong Dichotomy Conjecture. For every graph , the problem is either polynomial-time solvable for arbitrary input graphs, or it is NP-complete when the input is restricted to simple graphs. The conjecture is presented as an open dichotomy prediction; the paper notes that its NP-hardness theorem for regular trees provides further confirmation, but does not prove the conjecture in general.
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.