Graph homomorphism

A homomorphism from the flower snark J5 into the cycle graph C5.
It is also a retraction onto the subgraph on the central five vertices, so J5 is in fact homo­mor­phi­cally equivalent to the core C5.

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.

Homomorphism 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.[1]

Definitions

A graph homomorphism[2] f  from a graph G = (V(G), E(G)) to a graph H = (V(H), E(H)), written

f : G → H

is a mapping f : V(G) → V(H) such that {u,v} ∈ E(G) implies {f(u),f(v)} ∈ E(H), for all u, v ∈ V(G). If there exists any homomorphism f : G → H, then G is said to be homomorphic to H or H-colorable, we shall write:

G → H .

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.

If the homomorphism f : G → H is an injection, then G is simply a subgraph of H. If the homomorphism is a bijection whose inverse function is also a graph homomorphism, then f is a graph isomorphism.[3] If the homomorphism is a surjection that is locally bijective, that is, it is bijective on the neighbourhood of each vertex, then f is called a covering map, mirroring the definition and many properties of covering maps in topology.[4]

Cores and retracts

Two graphs G and H are homomorphically equivalent if G → H and H → G.

A retract of a graph G is a subgraph H of G such that there exists a homomorphism r : G → H (called a retraction) with r(x) = x for each vertex x of H. A core is a graph which does not retract to a proper subgraph. Equivalently, a core can be characterized as a graph that admits no homomorphism to any proper subgraph.[5] Any finite graph G is homomorphically equivalent to a unique core (up to isomorphism),[6] and contains it as retract and as an induced subgraph; it is called the core of G.[7]

For example, any 3-colorable graph G that contains a triangle (that is, has the complete graph K3 as a subgraph) is homomorphically equivalent to K3, which is a core. This is because a 3-coloring of G is the same as a homomorphism G → K3, as explained below, and every subgraph of G trivially admits a homomorphism into G, implying K3 → G. Similarly, every bipartite graph that has at least one edge is equivalent to K2.[8]

Connection to colorings

A k-coloring, for some integer k, is an assignment of one of k colors to each vertex of a graph G so that the endpoints of each edge have different colors. Each k-coloring corresponds to a homomorphism from G to the complete graph Kk.[9] Indeed, the vertices of Kk correspond to the k colors, and two colors are different if and only if they are adjacent as vertices of Kk (since Kk has edges between all possible different vertices and no edge from a vertex to itself). Hence a function maps adjacent vertices of G to different colors (is a valid k-coloring) if and only if it defines a homomorphism to Kk. In particular, G is k-colorable if and only if G → Kk.[9]

If there are two homomorphisms G → H → Kk, then their composition G → Kk is also a homomorphism.[10] In other words, if a graph H can be colored with k colors, and there is a homomorphism G → H, then G can also be k-colored. Therefore, G → H implies χ(G) ≤ χ(H), where χ denotes the chromatic number of a graph.[11]

Variants

General homomorphisms can also be thought of as a kind of coloring: if the vertices of a fixed graph H are the available colors and edges of H describe which colors are compatible, then an H-coloring of G is an assignment of colors to vertices of G such that adjacent vertices get compatible colors.

Many notions of graph coloring fit into this pattern and can be expressed as graph homomorphisms into different families of graphs. Circular colorings can be defined using homomorphisms into circular complete graphs, refining the usual notion of colorings.[12] Fractional and b-fold coloring can be defined using homomorphisms into Kneser graphs.[13] T-colorings correspond to homomorphisms into certain infinite graphs.[14] An oriented coloring of a directed graph is a homomorphism into any oriented graph.[15] An L(2,1)-coloring is a homomorphism into the complement of the path graph that is locally injective, meaning it is required to be injective on the neighbourhood of every vertex.[16]

Connection to constraint satisfaction problems

Examples

Graph H of non-consecutive weekdays, isomorphic to the complement graph of C7 and to the circular clique K7/2

Some scheduling problems can be modeled as a question about finding graph homomorphisms.[17][18] 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 C7. A graph homomorphism G → H is then a schedule assigning courses to time slots, as specified.[17] 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: 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 added to the edge of G, while 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.[19]

An example with a different flavor is part-of-speech tagging. Here the goal is to mark words in a longer text according to the part of speech they belong to (such as noun, verb, adjective). An algorithm with no knowledge of the language can construct a directed graph G whose vertices are words, adding an arc from any word to each word that occurs directly after it at any place in the text. The language can then be modeled with a directed graph H whose vertices are the possible parts of speech, with an arc from one part of speech to another whenever the pair can occur consecutively in grammatically correct sentences. A homomorphism from G to H then represents a way to assign a part of speech to each word so that these grammatical conditions are satisfied. A more quantitative and practical way to formalize similar problems is given by Hidden Markov models.

In each case, these simplified models display many of the issues that have to be handled in practice.[20] 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) to make the models more realistic and practical.

Formal view

Graphs and directed graphs can be viewed as a special case of the far more general notion called structures—they are structures with a single binary relation (adjacency) on the domain (the vertex set).[21][22] Under this view, homomorphisms of such structures are exactly graph homomorphisms. In general, the question of finding a homomorphism from one relational structure (a structure with no functions in the signature, only relations) to another is a constraint satisfaction problem (CSP). The case of graphs gives a concrete first step that helps to understand more complicated CSPs. Most algorithmic methods for finding graph homomorphisms, like backtracking, constraint propagation and local search, apply to all CSPs.[22]

For graphs G and H, the question of whether G → H holds corresponds to a CSP instance with only one kind of constraint,[22] 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)), that is, a constraint expressing that the evaluation should map the arc (u,v) to a pair (f(u),f(v)) which is in the relation E(H), a pair that is 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.[10] In particular, the relation → on graphs is transitive (and reflexive, trivially), so it is a preorder on graphs.[23] 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.[24]

It is a dense order, meaning that for every graphs G, H such that G → H and H ↛ G, there is a graph K such that G → K → H and H ↛ K ↛ G (this holds except for the trivial cases G = K0 or K1).[25][26] For example, between any two complete graphs (except K0, K1) there are infinitely many circular complete graphs in the order, corresponding to rational numbers between natural numbers.[27]

The poset of equivalence classes of graphs under homomorphisms is a distributive lattice, with the join of [G] and [H] defined as the disjoint union [G ∪ H], and the meet of [G] and [H] defined as the tensor product [G × H].[28] 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.[29] The meet-irreducible elements of this lattice are exactly the multiplicative graphs; identifying them lies at the heart of Hedetniemi's conjecture.[30][31]

Graph homomorphisms also form a category, with graphs as objects and homomorphisms as arrows.[32] 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.[31][33] Since these two operations are always defined, the category of graphs is a cartesian closed category. For the same reason, the lattice of equivalence classes of graphs under homomorphisms is in fact a Heyting algebra.[31][33]

Incomparable graphs

The Grötzsch graph, incomparable to K3

There are many incomparable graphs with respect to the homomorphism preorder, that is, graphs G, H such that G ↛ H and H ↛ G.[34] One way to construct them is to consider the odd girth of a graph G, the length of its shortest odd-length cycle. The odd girth is, equivalently, the smallest odd number g for which there exists a homomorphism Cg → G. For this reason, if G → H, then the odd girth of G is greater than or equal to the corresponding invariant of H.[35]

On the other hand, if G → H, then the chromatic number of G is less than or equal to the corresponding invariant of G. Therefore, if G has strictly larger odd girth than H and strictly larger chromatic number than H, then G ↛ H and H ↛ G.[34] For example, the Grötzsch graph is 4-chromatic and triangle-free (it has girth 4 and odd girth 5),[36] so it is incomparable to the triangle graph K3.

Examples of graphs with arbitrarily large values of odd girth and chromatic number are Kneser graphs[37] and generalized Mycielskians.[38] A sequence of such graphs, with simultaneously increasing values of both parameters, gives infinitely many incomparable graphs (an antichain in the homomorphism preorder).[39] Other properties, such as density of the homomorphism preorder, can be proved using such families.[40] 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).

Computational complexity

In the graph homomorphism problem, an instance is a pair of graphs (G,H) and a solution is a homomorphism G → H, from the 'left' graph to the 'right' graph. The general decision problem, asking whether there is any solution is NP-complete.[41] 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 are very different than for the 'right' side, 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 Kk, this is the graph k-coloring problem, which is solvable in polynomial time for k = 0, 1, 2, and NP-complete otherwise.[42] In particular, K2-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 K2-colorability (or K0 / K1-colorability when H is empty/edgeless), hence equally easy to decide.[43] 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.[44][45]

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.[46] 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.[47][48] 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.[48]

Intuitively, this means that any algorithmic techniques or complexity results that apply to H-coloring problems for directed graphs H apply just as well to general CSPs (in other words, to arbitrary relational structures in place of H). In particular, the question whether the Hell-Nešetřil theorem can be extended to directed graphs is equivalent to the Feder-Vardi conjecture on CSP dichotomy, which states that for every constraint language Γ, CSP(Γ) is either in P or NP-complete.[41]

Homomorphisms from a fixed family of graphs

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. 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. For graphs G of treewidth at most k and any 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 G is homomorphically equivalent to a graph of treewidth at most k, even if this graph is not known (nor a homomorphism to it or a tree decomposition of it).[49][50] There are essentially no other properties that can be used to get polynomial time algorithms, assuming the exponential time hypothesis (ETH):

Theorem (Grohe): For a computable class of graph , the homomorphism problem for instances with is in P if and only if graphs in are homomorphically equivalent to graphs of bounded treewidth (assuming ETH).[50]

Moreover, the homomorphism problem in parameterized by the size (number of edges) of G exhibits a dichotomy: it is fixed-parameter tractable if graphs in are homomorphically equivalent to graphs of bounded treewidth, and W[1]-complete otherwise. It is also known that exploiting other properties cannot even lower the exponent in the |V(H)|O(k)-time algorithm significantly: for any class of graph , no algorithm with running time |V(H)|o(tw(G) /log tw(G)) exists, assuming ETH.[51]

The same statements hold more generally for all constraint satisfaction problems (or all relational structures, in other words), assuming that constraints can involve only a bounded number of variables (all relations are of some bounded arity, 2 in the case of graphs). The relevant parameter is then the treewidth of the primal constraint graph.[51]

Determining whether there is an isomorphism between two graphs is also an important problem in computational complexity theory; see graph isomorphism problem.

See also

Notes

  1. ↑ Hell & Nešetřil 2004, p. 27.
  2. ↑ For introductions, see (in order of increasing length): Cameron (2006); Geňa & Tardif (1997); Hell & Nešetřil (2004).
  3. ↑ Geňa & Tardif 1997, Observation 2.3.
  4. ↑ Godsil & Royle 2001.
  5. ↑ Hell & Nešetřil 2004, Proposition 1.31.
  6. ↑ Cameron 2006, Proposition 2.3; Hell & Nešetřil 2004, Corollary 1.32.
  7. ↑ Hell & Nešetřil 2004, p. 19.
  8. ↑ Cameron 2006, p. 4, Proposition 2.5.
  9. 1 2 Cameron 2006, p. 1; Hell & Nešetřil 2004, Proposition 1.7.
  10. 1 2 Hell & Nešetřil 2004, §1.7.
  11. ↑ Hell & Nešetřil 2004, Corollary 1.8.
  12. ↑ Hell & Nešetřil 2004, §6.1; Geňa & Tardif 1997, §4.4.
  13. ↑ Hell & Nešetřil 2004, §6.2; Geňa & Tardif 1997, §4.5.
  14. ↑ Hell & Nešetřil 2004, §6.3.
  15. ↑ Hell & Nešetřil 2004, §6.4.
  16. ↑ Fiala, J.; Kratochvíl, J. (2002), "Partial covers of graphs", Discussiones Mathematicae Graph Theory, 22 (1): 89–99
  17. 1 2 Cameron 2006, p. 1.
  18. ↑ Hell & Nešetřil 2004, §1.8.
  19. ↑ Hell & Nešetřil 2004, pp. 30–31.
  20. ↑ Hell & Nešetřil 2004, pp. 31–32.
  21. ↑ Hell & Nešetřil 2004, p. 28, note relational structures are called relational systems there.
  22. 1 2 3 Hell, Pavol; Nešetřil, Jaroslav (2008), "Colouring, constraint satisfaction, and complexity" (PDF), Computer Science Review, 2 (2): 143–163, doi:10.1016/j.cosrev.2008.10.003
  23. ↑ Hell & Nešetřil 2004, §3.1.
  24. ↑ Hell & Nešetřil 2004, Theorem 3.1.
  25. ↑ Hell & Nešetřil 2004, Theorem 3.30; Geňa & Tardif 1997, Theorem 2.33.
  26. ↑ Welzl, E. (1982), "Color-families are dense", Theoret. Comput. Sci., 17: 29–41
  27. ↑ Hell & Nešetřil 2004, p. 192; Geňa & Tardif 1997, p. 127.
  28. ↑ Hell & Nešetřil 2004, Proposition 3.2, distributivity is stated in Proposition 2.4; Geňa & Tardif 1997, Theorem 2.37.
  29. ↑ Gray 2014, Lemma 3.7.
  30. ↑ Tardif, C. (2008), "Hedetniemi's conjecture, 40 years later" (PDF), Graph Theory Notes of New York, 54: 46–57, MR 2445666.
  31. 1 2 3 Dwight, D.; Sauer, N. (1996), "Lattices arising in categorial investigations of Hedetniemi's conjecture", Discrete Math., 152 (1-3): 125–139, doi:10.1016/0012-365X(94)00298-W
  32. ↑ Hell & Nešetřil 2004, p. 125.
  33. 1 2 Gray 2014.
  34. 1 2 Hell & Nešetřil 2004, p. 7.
  35. ↑ Geňa & Tardif 1997, Observation 2.6.
  36. ↑ Weisstein, Eric Wolfgang. "Grötzsch Graph". MathWorld.
  37. ↑ Geňa & Tardif 1997, Proposition 3.14.
  38. ↑ Gyárfás, A.; Jensen, T.; Stiebitz, M. (2004), "On Graphs With Strongly Independent Color-Classes", J. Graph Theory, 46 (1): 1–14, doi:10.1002/jgt.10165
  39. ↑ Hell & Nešetřil 2004, Proposition 3.4.
  40. ↑ Hell & Nešetřil 2004, p. 96.
  41. 1 2 Bodirsky, M. (2007), Graph Homomorphisms and Universal Algebra, Course Notes (PDF), §1.3.
  42. ↑ Hell & Nešetřil 2004, §5.1.
  43. ↑ Hell & Nešetřil 2004, Proposition 5.1.
  44. ↑ Hell & Nešetřil 2004, §5.2.
  45. ↑ Hell, Pavol; Nešetřil, Jaroslav (1990), "On the complexity of H-coloring", JCTB, 48 (1): 92–110, doi:10.1016/0095-8956(90)90132-J Freely accessible
  46. ↑ Hell & Nešetřil 2004, §5.3.
  47. ↑ Hell & Nešetřil 2004, Theorem 5.14.
  48. 1 2 Feder, Tomás; Vardi, Moshe Y. (1998), "The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory", SIAM J. Comput., 28 (1): 57–104, doi:10.1137/S0097539794266766
  49. ↑ Dalmau, Víctor; Kolaitis, Phokion G.; Vardi, Moshe Y. (2002). Constraint Satisfaction, Bounded Treewidth, and Finite-Variable Logics. 8th International Conference on Principles and Practice of Constraint Programming (CP 2002). pp. 310–326. doi:10.1007/3-540-46135-3_21.
  50. 1 2 Grohe, Martin (2007), "The complexity of homomorphism and constraint satisfaction problems seen from the other side", J. ACM, 54 (1), doi:10.1145/1206035.1206036
  51. 1 2 Marx, Dániel (2010), "Can You Beat Treewidth?", Theory of Computing, 6: 85–112, doi:10.4086/toc.2010.v006a005 Freely accessible

References

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.