Algorithm for graph homomorphisms

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

For finite simple input graphs $G,H$, a homomorphism is a map $f:V(G)\to V(H)$ sending every edge of $G$ to an edge of $H$. The constant in a uniform time bound must be independent of both input graphs.

Statement recorded in the supplied source.

Is there an algorithm and an absolute constant $c>1$ deciding whether $G\to H$ in time $O(c^{|V(G)|+|V(H)|})$ for all input pairs? [S2]

Short English statement

Can unrestricted graph homomorphism be decided in time exponential only in the combined number of vertices?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 3210 (OPG-37232). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Algorithm for graph homomorphisms, original node 37232, statement and mathematical discussion. https://www.openproblemgarden.org/op/algorithm_for_graph_homomorphisms.