Publication
Complexity of the Graph Homomorphism Problem w.r.t. Degeneracy
ECCC TR26-122, 2026. PDF ยท Official record
Abstract
The graph homomorphism problem \(\mathrm{HOM}\) asks whether an \(n\)-vertex source graph \(G\) maps to an \(h\)-vertex target graph \(H\) while preserving edges. A straightforward algorithm has running time \(O(2^{n\log h})\), and under ETH there are no \(2^{o(n\log h)}\) algorithms. We study the complexity of \(\mathrm{HOM}\) in terms of the degeneracy of \(H\), a natural graph parameter between the known algorithmic and hardness regimes.
We show that, under ETH, there is no \(2^{o(\operatorname{degen}(H)n)}\) algorithm for any value of \(\operatorname{degen}(H)\) as a function of \(n\). Bounded degeneracy alone does not make target size benign: even targets of degeneracy at most two and quasi-polynomial size force \(n^{\Omega(n)}\)-scale hardness. Finally, we introduce a no-compression barrier explaining why known fine-grained lower bounds for sparse 2-CSP are not tight under ETH.