Strong Dichotomy Conjecture for graph covers

For every graph $H$ , consider the problem $\textsc{H-Cover}$ of deciding whether an input graph covers $H$ . Strong Dichotomy Conjecture. For every graph $H$ , the problem $\textsc{H-Cover}$ 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 1

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 $H$ be a graph. The problem ${\sc H\text{-}Cover}$ asks whether an input graph admits a cover mapping to $H$ .

Strong dichotomy conjecture. For every graph $H$ , the ${\sc H\text{-}Cover}$ 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 ${\sc H\text{-}Cover}$ 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).

Sources & referencesView supporting material

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.

1 week ago

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

No solutions have been posted yet.

Equivalent formulations 1