6 - Algorithmic aspects of graph homomorphisms

Summary

Abstract

Homomorphisms are a useful model for a wide variety of combinatorial problems dealing with mappings and assignments, typified by scheduling and channel assignment problems. Homomorphism problems generalize graph colourings, and are in turn generalized by constraint satisfaction problems; they represent a robust intermediate class of problems – with greater modeling power than graph colourings, yet simpler and more manageable than general constraint satisfaction problems. We will discuss various homomorphism problems from a computational perspective. One variant, with natural applications, gives each vertex a list of allowed images. Such list homomorphisms generalize list colourings, precolouring extensions, and graph retractions. Many algorithms for finding homomorphisms adapt well to finding list homomorphisms. Semi-homomorphisms are another variant; they generalize the kinds of partitions that homomorphisms induce, to allow both homomorphism type constraints, and constraints that correspond to homomorphisms of the complementary graphs. Surprisingly, semi-homomorphism partition problems cover a great variety of concepts arising in the study of perfect graphs. We illustrate some of the ideas leading to efficient algorithms for all these problems.

Introduction

Graphs we consider may be directed or undirected, and, correspondingly, uv can denote a directed arc or an undirected edge, depending on the context. Both kinds of graphs will be allowed to have loops, but no parallel edges, and all graphs will be assumed to be finite. A homomorphism of a graph G to a graph H is a mapping f: V(G) → V(H) such that uv ∈ (G) implies f(u)f(v) ∈ E(H).