Graph homomorphism

[2] The computational complexity of finding a homomorphism between given graphs is prohibitive in general, but a lot is known about special cases that are solvable in polynomial time.

Two graphs G and H are homomorphically equivalent if G → H and H → G.[4] The maps are not necessarily surjective nor injective.

For instance, the complete bipartite graphs K2,2 and K3,3 are homomorphically equivalent: each map can be defined as taking the left (resp.

Hence a function defines a homomorphism to Kk if and only if it maps adjacent vertices of G to different colors (i.e., it is a k-coloring).

[15] Fractional and b-fold coloring can be defined using homomorphisms into Kneser graphs.

An example of an orientation of the complete graph Kk is the transitive tournament T→k with vertices 1,2,…,k and arcs from i to j whenever i < j.

This statement can be strengthened slightly to say that a graph is k-colorable if and only if some orientation contains no directed path of length k (no P→k+1 as a subgraph).

For instance, if one wants a cyclical, weekly schedule, such that each student gets their workshop courses on non-consecutive days, then H would be the complement graph of C7.

[22] To add a requirement saying that, e.g., no single student has courses on both Friday and Monday, it suffices to remove the corresponding edge from H. A simple frequency allocation problem can be specified as follows: a number of transmitters in a wireless network must choose a frequency channel on which they will transmit data.

If this condition is approximated with a single threshold to define 'geographically close' and 'far apart', then a valid channel choice again corresponds to a graph homomorphism.

While this model is rather simplified, it does admit some flexibility: transmitter pairs that are not close but could interfere because of geographical features can be added to the edges of G. Those that do not communicate at the same time can be removed from it.

Similarly, channel pairs that are far apart but exhibit harmonic interference can be removed from the edge set of H.[24] In each case, these simplified models display many of the issues that have to be handled in practice.

Directed graphs are structures with a single binary relation (adjacency) on the domain (the vertex set).

In general, the question of finding a homomorphism from one relational structure to another is a constraint satisfaction problem (CSP).

The case of graphs gives a concrete first step that helps to understand more complicated CSPs.

Many algorithmic methods for finding graph homomorphisms, like backtracking, constraint propagation and local search, apply to all CSPs.

[3] For graphs G and H, the question of whether G has a homomorphism to H corresponds to a CSP instance with only one kind of constraint,[3] as follows.

For the same reason, the lattice of equivalence classes of graphs under homomorphisms is in fact a Heyting algebra.

The order → for directed graphs is again a distributive lattice and a Heyting algebra, with join and meet operations defined as before.

[40] One way to construct them is to consider the odd girth of a graph G, the length of its shortest odd-length cycle.

There is a homomorphism from C→n to C→k (n, k ≥ 3) if and only if n is a multiple of k. In particular, directed cycle graphs C→n with n prime are all incomparable.

[48] However, limiting allowed instances gives rise to a variety of different problems, some of which are much easier to solve.

More generally, whenever H is a bipartite graph, H-colorability is equivalent to K2-colorability (or K0 / K1-colorability when H is empty/edgeless), hence equally easy to decide.

[50] Pavol Hell and Jaroslav Nešetřil proved that, for undirected graphs, no other case is tractable: This is also known as the dichotomy theorem for (undirected) graph homomorphisms, since it divides H-coloring problems into NP-complete or P problems, with no intermediate cases.

For directed graphs, the situation is more complicated and in fact equivalent to the much more general question of characterizing the complexity of constraint satisfaction problems.

[53] It turns out that H-coloring problems for directed graphs are just as general and as diverse as CSPs with any other kinds of constraints.

By the above theorem, this is equivalent to the Feder–Vardi conjecture (aka CSP conjecture, dichotomy conjecture) on CSP dichotomy, which states that for every constraint language Γ, CSP(Γ) is NP-complete or in P.[48] This conjecture was proved in 2017 independently by Dmitry Zhuk and Andrei Bulatov, leading to the following corollary: The homomorphism problem with a single fixed graph G on left side of input instances can be solved by brute-force in time |V(H)|O(|V(G)|), so polynomial in the size of the input graph H.[56] In other words, the problem is trivially in P for graphs G of bounded size.

[57][58] The exponent in the |V(H)|O(k)-time algorithm cannot be lowered significantly: no algorithm with running time |V(H)|o(tw(G) /log tw(G)) exists, assuming the exponential time hypothesis (ETH), even if the inputs are restricted to any class of graphs of unbounded treewidth.

This is formalized as follows: One can ask whether the problem is at least solvable in a time arbitrarily highly dependent on G, but with a fixed polynomial dependency on the size of H. The answer is again positive if we limit G to a class of graphs with cores of bounded treewidth, and negative for every other class.

The same statements hold more generally for constraint satisfaction problems (or for relational structures, in other words).