Langberg, Michael and Rabani, Yuval and Swamy, Chaitanya
(2006)
*Approximation Algorithms for Graph Homomorphism Problems.*
In:
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques.
Lecture Notes in Computer Science.
No.4110.
Springer
, Berlin, pp. 176-187.
ISBN 978-3-540-38044-3.
https://resolver.caltech.edu/CaltechAUTHORS:20191112-105626756

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20191112-105626756

## Abstract

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 φ′:U↦V_H, U⊆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 ≃ 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.

Item Type: | Book Section | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|

Related URLs: |
| ||||||||||

ORCID: |
| ||||||||||

Additional Information: | © 2006 Springer-Verlag Berlin Heidelberg. Research supported in part by NSF grant CCF-0346991. Supported in part by ISF 52/03, BSF 2002282, and the Fund for the Promotion of Research at the Technion. Part of this work was done while visiting Caltech. | ||||||||||

Funders: |
| ||||||||||

Subject Keywords: | Approximation Algorithm; Random Graph; Linear Programming Relaxation; Label Graph; Graph Homomorphism | ||||||||||

Series Name: | Lecture Notes in Computer Science | ||||||||||

Issue or Number: | 4110 | ||||||||||

DOI: | 10.1007/11830924_18 | ||||||||||

Record Number: | CaltechAUTHORS:20191112-105626756 | ||||||||||

Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20191112-105626756 | ||||||||||

Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | ||||||||||

ID Code: | 99807 | ||||||||||

Collection: | CaltechAUTHORS | ||||||||||

Deposited By: | Tony Diaz | ||||||||||

Deposited On: | 12 Nov 2019 22:55 | ||||||||||

Last Modified: | 16 Nov 2021 17:49 |

Repository Staff Only: item control page