Approximation Algorithms for Graph Homomorphism Problems

We introduce the

maximum graph homomorphism

(MGH) problem: given a graph

G

, and a target graph

H

, find a mapping

ϕ

:

V

G

↦

V

H

that maximizes the number of edges of

G

that are mapped to edges of

H

. This problem encodes various fundamental NP-hard problems including Maxcut and Max-

k

-cut. We also consider the

multiway uncut

problem. We are given a graph

G

and a set of terminals

T

 ⊆ 

V

G

. We want to partition

V

G

into |

T

| parts, each containing exactly one terminal, so as to maximize the number of edges in

E

G

having both endpoints in the same part. Multiway uncut can be viewed as a special case of

prelabeled

MGH where one is also given a prelabeling

${\ensuremath{\varphi}}':U\mapsto V_H,\ U{\subseteq} V_G$

, and the output has to be an extension of

ϕ

′.

Both MGH and multiway uncut have a trivial 0.5-approximation algorithm. We present a 0.8535-approximation algorithm for multiway uncut based on a natural linear programming relaxation. This relaxation has an integrality gap of

$\frac{6}{7}\simeq 0.8571$

, showing that our guarantee is almost tight. For maximum graph homomorphism, we show that a

$\bigl({\ensuremath{\frac{1}{2}}}+{\ensuremath{\varepsilon}}_0)$

-approximation algorithm, for any constant

ε

0

 > 0, implies an algorithm for distinguishing between certain average-case instances of the

subgraph isomorphism

problem that appear to be hard. Complementing this, we give a

$\bigl({\ensuremath{\frac{1}{2}}}+\Omega(\frac{1}{|H|\log{|H|}})\bigr)$

-approximation algorithm.