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-hardproblems 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 is contained in 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 φ′ : U ∣→ V_H, U is contained in 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 6/7 approx= 0.8571, showing that our guarantee is almost tight. For maximum graph homomorphism, we show that a (1/2 + ε_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 (1/2 + Ω(1/(∣H∣log∣H∣)))-approximation algorithm.
展开▼
