Strong Dichotomy Conjecture for graph covers
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.
Equivalent formulations 1Other wordings
Other statements of this same problem, merged from separate entries. Each is equivalent to the statement above — proving any one settles them all.
Strong dichotomy conjecture for graph covers
Let be a graph. The problem asks whether an input graph admits a cover mapping to .
Strong dichotomy conjecture. For every graph , the problem is either polynomial-time solvable for arbitrary input graphs, or it is NP-complete for simple graphs as input.
All known NP-hard instances of remain NP-hard for simple input graphs, motivating this conjecture. Its general status is not specified in the source.
source: Jan Bok, Jiří Fiala, Nikola Jedličková, Jan Kratochvíl and Micheala Seifrtová, “Computational Complexity of Covering Colored Mixed Multigraphs with Simple Degree Partitions”, arXiv:2502.20151 (2025).
References
Primary source
Jan Bok, Jiří Fiala, Nikola Jedličková and Jan Kratochvíl, “Computational complexity of covering regular trees”, arXiv:2507.00564 (2025).
Additional references
2 papers in this index state this conjecture (2022–2025). The statement above is taken from the most recent of them; the others are arXiv:2204.04280.
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
No solutions have been posted yet.