Graph homomorphism

upright=1.2|thumb|alt= Graph homomorphism from J5 into C5|A homomorphism from the [[flower snark J₅ into the cycle graph C₅.<br/>It is also a retraction onto the subgraph on the central five vertices. Thus J₅ is in fact equivalent to the core C₅.]]

In the mathematical field of graph theory, a graph homomorphism is a mapping between two graphs that respects their structure. More concretely, it is a function between the vertex sets of two graphs that maps adjacent vertices to adjacent vertices.

Homomorphisms generalize various notions of graph colorings and allow the expression of an important class of constraint satisfaction problems, such as certain scheduling or frequency assignment problems.

The fact that homomorphisms can be composed leads to rich algebraic structures: a preorder on graphs, a distributive lattice, and a category (one for undirected graphs and one for directed graphs).

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. Boundaries between tractable and intractable cases have been an active area of research.

Definitions

In this article, unless stated otherwise, graphs are finite, undirected graphs with loops allowed, but multiple edges (parallel edges) disallowed.

A graph homomorphism &nbsp; from a graph <math>G = (V(G), E(G))</math> to a graph <math> H = (V(H), E(H))</math>, written , is a function from <math>V(G)</math> to <math>V(H)</math> that preserves edges. Formally,

<math>(u,v) \in E(G)</math> implies <math>(f(u),f(v)) \in E(H)</math>, for all pairs of vertices <math>u, v</math> in <math>V(G)</math>.

If there exists any homomorphism from G to H, then G is said to be homomorphic to H or H-colorable. This is often denoted as just

:

The above definition is extended to directed graphs. Then, for a homomorphism f : G → H, (f(u),f(v)) is an arc (directed edge) of H whenever (u,v) is an arc of G.

There is an injective homomorphism from G to H (i.e., one that maps distinct vertices in G to distinct vertices in H) if and only if G is isomorphic to a subgraph of H.

If a homomorphism f : G → H is a bijection, and its inverse function is also a graph homomorphism, then f is a graph isomorphism.

Covering maps are a special kind of homomorphisms that mirror the definition and many properties of covering maps in topology.

They are defined as surjective homomorphisms (i.e., something maps to each vertex) that are also locally bijective, that is, a bijection on the neighbourhood of each vertex.

An example is the bipartite double cover, formed from a graph by splitting each vertex v into v₀ and v₁ and replacing each edge u,v with edges u₀,v₁ and v₀,u₁. The function mapping v₀ and v₁ in the cover to v in the original graph is a homomorphism and a covering map.

Graph homeomorphism is a different notion, not related directly to homomorphisms. Roughly speaking, it requires injectivity, but allows mapping edges to paths (not just to edges). Graph minors are a still more relaxed notion.

Cores and retracts

thumb|upright=0.8|right|K₇, the complete graph with 7 vertices, is a core.

Two graphs G and H are homomorphically equivalent if

G → H and H → G.

Orientations without long paths

Another interesting connection concerns orientations of graphs.

An orientation of an undirected graph G is any directed graph obtained by choosing one of the two possible orientations for each edge.

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

A homomorphism between orientations of graphs G and H yields a homomorphism between the undirected graphs G and H, simply by disregarding the orientations.

On the other hand, given a homomorphism G → H between undirected graphs, any orientation of H can be pulled back to an orientation of G so that has a homomorphism to .

Therefore, a graph G is k-colorable (has a homomorphism to K_k) if and only if some orientation of G has a homomorphism to _k.

A folklore theorem states that for all k, a directed graph G has a homomorphism to _k if and only if it admits no homomorphism from the directed path _k+1.

Here _n is the directed graph with vertices 1, 2, …, n and edges from i to i + 1, for i = 1, 2, …, n − 1.

Therefore, a graph is k-colorable if and only if it has an orientation that admits no homomorphism from _k+1.

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 _k+1 as a subgraph).

This is the Gallai–Hasse–Roy–Vitaver theorem.

Connection to constraint satisfaction problems

Examples

thumb|Graph H of non-consecutive weekdays, isomorphic to the [[complement graph of C₇ and to the circular clique K_7/2]]

Some scheduling problems can be modeled as a question about finding graph homomorphisms. As an example, one might want to assign workshop courses to time slots in a calendar so that two courses attended by the same student are not too close to each other in time. The courses form a graph G, with an edge between any two courses that are attended by some common student. The time slots form a graph H, with an edge between any two slots that are distant enough in time. 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 C₇. A graph homomorphism from G to H is then a schedule assigning courses to time slots, as specified. 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. To avoid interference, transmitters that are geographically close should use channels with frequencies that are far apart. 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. It should go from the graph of transmitters G, with edges between pairs that are geographically close, to the graph of channels H, with edges between channels that are far apart. 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.

In each case, these simplified models display many of the issues that have to be handled in practice. Constraint satisfaction problems, which generalize graph homomorphism problems, can express various additional types of conditions (such as individual preferences, or bounds on the number of coinciding assignments). This allows the models to be made more realistic and practical.

Formal view

Graphs and directed graphs can be viewed as a special case of the far more general notion called relational structures (defined as a set with a tuple of relations on it). Directed graphs are structures with a single binary relation (adjacency) on the domain (the vertex set). Under this view, homomorphisms of such structures are exactly graph homomorphisms.

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.

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, as follows. The variables are the vertices of G and the domain for each variable is the vertex set of H. An evaluation is a function that assigns to each variable an element of the domain, so a function f from V(G) to V(H). Each edge or arc (u,v) of G then corresponds to the constraint ((u,v), E(H)). This is a constraint expressing that the evaluation should map the arc (u,v) to a pair (f(u),f(v)) that is in the relation E(H), that is, to an arc of H. A solution to the CSP is an evaluation that respects all constraints, so it is exactly a homomorphism from G to H.

Structure of homomorphisms

Compositions of homomorphisms are homomorphisms.

In particular, the relation → on graphs is transitive (and reflexive, trivially), so it is a preorder on graphs.

Let the equivalence class of a graph G under homomorphic equivalence be [G].

The equivalence class can also be represented by the unique core in [G].

The relation → is a partial order on those equivalence classes; it defines a poset.

Let G < H denote that there is a homomorphism from G to H, but no homomorphism from H to G.

The relation → is a dense order, meaning that for all (undirected) graphs G, H such that G < H, there is a graph K such that G < K < H (this holds except for the trivial cases G = K₀ or K₁).

For example, between any two complete graphs (except K₀, K₁, K₂) there are infinitely many circular complete graphs, corresponding to rational numbers between natural numbers.

The poset of equivalence classes of graphs under homomorphisms is a distributive lattice, with the join of [G] and [H] defined as (the equivalence class of) the disjoint union [G ∪ H], and the meet of [G] and [H] defined as the tensor product [G × H] (the choice of graphs G and H representing the equivalence classes [G] and [H] does not matter).

The join-irreducible elements of this lattice are exactly connected graphs. This can be shown using the fact that a homomorphism maps a connected graph into one connected component of the target graph.

The meet-irreducible elements of this lattice are exactly the multiplicative graphs. These are the graphs K such that a product G × H has a homomorphism to K only when one of G or H also does. Identifying multiplicative graphs lies at the heart of Hedetniemi's conjecture.

Graph homomorphisms also form a category, with graphs as objects and homomorphisms as arrows.

The initial object is the empty graph, while the terminal object is the graph with one vertex and one loop at that vertex.

The tensor product of graphs is the category-theoretic product and

the exponential graph is the exponential object for this category. so it is incomparable to the triangle graph K₃.

Examples of graphs with arbitrarily large values of odd girth and chromatic number are Kneser graphs and generalized Mycielskians.

A sequence of such graphs, with simultaneously increasing values of both parameters, gives infinitely many incomparable graphs (an antichain in the homomorphism preorder).

Other properties, such as density of the homomorphism preorder, can be proved using such families.

Constructions of graphs with large values of chromatic number and girth, not just odd girth, are also possible, but more complicated (see Girth and graph coloring).

Among directed graphs, it is much easier to find incomparable pairs. For example, consider the directed cycle graphs _n, with vertices 1, 2, …, n and edges from i to i + 1 (for i = 1, 2, …, n − 1) and from n to 1.

There is a homomorphism from _n to _k (n, k ≥ 3) if and only if n is a multiple of k.

In particular, directed cycle graphs _n with n prime are all incomparable.

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.

Homomorphisms to a fixed graph

The homomorphism problem with a fixed graph H on the right side of each instance is also called the H-coloring problem. When H is the complete graph K_k, this is the graph k-coloring problem, which is solvable in polynomial time for k = 0, 1, 2, and NP-complete otherwise.

In particular, K₂-colorability of a graph G is equivalent to G being bipartite, which can be tested in linear time.

More generally, whenever H is a bipartite graph, H-colorability is equivalent to K₂-colorability (or K₀ / K₁-colorability when H is empty/edgeless), hence equally easy to decide.

Pavol Hell and Jaroslav Nešetřil proved that, for undirected graphs, no other case is tractable:

: Hell–Nešetřil theorem (1990): The H-coloring problem is in P when H is bipartite and NP-complete otherwise.

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.

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. Formally, a (finite) constraint language (or template) Γ is a finite domain and a finite set of relations over this domain. CSP(Γ) is the constraint satisfaction problem where instances are only allowed to use constraints in Γ.

: Theorem (Feder, Vardi 1998): For every constraint language Γ, the problem CSP(Γ) is equivalent under polynomial-time reductions to some H-coloring problem, for some directed graph H. In other words, the problem is trivially in P for graphs G of bounded size. The interesting question is then what other properties of G, beside size, make polynomial algorithms possible.

The crucial property turns out to be treewidth, a measure of how tree-like the graph is. For a graph G of treewidth at most k and a graph H, the homomorphism problem can be solved in time |V(H)|^O(k) with a standard dynamic programming approach. In fact, it is enough to assume that the core of G has treewidth at most k. This holds even if the core is not known.

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.

The ETH is an unproven assumption similar to P ≠ NP, but stronger.

Under the same assumption, there are also essentially no other properties that can be used to get polynomial time algorithms. This is formalized as follows:

: Theorem (Grohe): For a computable class of graphs <math>\mathcal{G}</math>, the homomorphism problem for instances <math>(G,H)</math> with <math>G \in \mathcal{G}</math> is in P if and only if graphs in <math>\mathcal{G}</math> have cores of bounded treewidth (assuming ETH).