Graph homomorphism
Computational complexity

In the graph homomorphism problem, an instance is a pair of graphs (G, H) and a solution is a homomorphism from G to H. The general decision problem, asking whether there is any solution, is NP-complete. However, limiting allowed instances gives rise to a variety of different problems, some of which are much easier to solve. Methods that apply when restraining the left side G are very different than for the right side H, but in each case a dichotomy (a sharp boundary between easy and hard cases) is known or conjectured.
length_constraints:number_sentences[12]