TR95-011 Authors: Roman Bacik, Sanjeev Mahajan

Publication: 21st February 1995 22:09

Downloads: 1819

Keywords:

The graph homomorphism problem is a canonical $NP$-complete problem.

It generalizes various other well-studied problems such as graph

coloring and finding cliques. To get a better insight into a

combinatorial problem, one often studies relaxations of the problem.

We define fractional homomorphisms and pseudo-homomorphisms as natural

relaxations of graph homomorphisms.

In their paper Feige and Lovasz defined a semidefinite relaxation of

the homomorphism problem, which allowed them to obtain polynomial time

algorithms for certain special cases of the problem. Their relaxation

is defined in terms of the solution to a semidefinite program. Hence a

characterization of their relaxation in terms of known combinatorial

notions is desirable. We show that our pseudo-homomorphism is

equivalent to the relaxation defined by Feige and Lovasz.

Our definition of pseudo-homomorphism involves the classical theta

number first defined by Lovasz. Although general graph homomorphism

does not admit a simple forbidden subgraph characterization,

surprisingly we can show that there is a simple forbidden subgraph

characterization (the forbidden subgraph is a clique in this case) of

the fractional homomorphism. As a byproduct, we obtain a simpler proof

of the NP hardness of the fractional chromatic number, first proved

by Grotschel, Lovasz and Schrijver using the ellipsoid method. Finally, we briefly discuss how to apply these techniques to general

NP problems and describe a unified setting in which a wide variety of seemingly disparate polynomial time problems can be decided.