Exact Algorithms for Graph Homomorphisms |
| |
Authors: | Fedor V Fomin Pinar Heggernes Dieter Kratsch |
| |
Affiliation: | (1) Department of Informatics, University of Bergen, N-5020 Bergen, Norway;(2) Laboratoire d'Informatique Theorique et Appliquee, Universite Paul Verlaine, 57045 Metz Cedex 01, France |
| |
Abstract: | Graph homomorphism, also called H-coloring, is a natural generalization of graph coloring: There is a
homomorphism from a graph G to a complete graph on k vertices if and only if G is k-colorable. During recent years the topic
of exact (exponential-time) algorithms for NP-hard problems in general, and for graph coloring in particular, has led to
extensive research. Consequently, it is natural to ask how the techniques developed for exact graph coloring algorithms can
be extended to graph homomorphisms. By the celebrated result of Hell and Nesetril, for each fixed simple graph H, deciding
whether a given simple graph G has a homomorphism to H is polynomial-time solvable if
H is a bipartite graph, and NP-complete otherwise. The case where H is the cycle of length 5, is the first NP-hard case different
from graph coloring. We show that for an odd integer
, whether an input graph G with n vertices is homomorphic to the cycle of length k, can be decided in time
. We extend the results obtained for cycles, which are graphs of treewidth two, to graphs of bounded treewidth as follows:
if H is of treewidth at most t, then whether input graph G with n vertices is homomorphic to H can be decided in time
. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|