Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > DEGENERACY:
Reports tagged with degeneracy:
TR26-122 | 10th July 2026
Grigorii Braulov, Nikolai Chukhin, Alexander Kulikov, Ivan Mihajlin

Complexity of the Graph Homomorphism Problem w.r.t. Degeneracy

The graph homomorphism problem HOM is: given an $n$-vertex source graph $G$ and an $h$-vertex target graph $H$, is there a mapping from $V(G)$ to $V(H)$ that preserves edges? A straightforward brute-force algorithm for HOM has running time $O(2^{n \log h})$ and it is known that, under ETH, there are ... more >>>




ISSN 1433-8092 | Imprint