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
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
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.
Source: Jan Bok, Jiří Fiala, Nikola Jedličková and Jan Kratochvíl, “Computational complexity of covering regular trees”, arXiv:2507.00564 (2025).
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.