Hardness of Approximation Between P and NP by Aviad Rubinstein

Author:Aviad Rubinstein
Language: eng
Format: epub
Publisher: Association for Computing Machinery and Morgan & Claypool Publishers
Published: 2019-03-14T16:00:00+00:00

12.1 Construction (and Completeness)

12.1.1 Construction

Let ψ be the 2CSP instance produced by the reduction in Theorem 2.2, i.e., a constraint graph over n variables with alphabet A of constant size. We construct the following graph Gψ = (V, E):

• Let ρ := log log n and .

• Vertices of Gψ correspond to all possible assignments (colorings) to all ρ-tuples of variables in ψ, i.e., V = [n]ρ × Aρ. Each vertex is of the form where {x1,…, xρ} are the chosen variables of v, and is the corresponding assignment to variable xi.

• If v ∈ V violates any 2CSP constraints, i.e., if there is a constraint on (xi, xj) in ψ that is not satisfied by , then v is an isolated vertex in Gψ.

• Let and . (u, v) ∈ E iff:

■ (u, v) does not violate any consistency constraints: for every shared variable xi, the corresponding assignments agree, ; and

■ (u, v) also does not violate any 2CSP constraints: for every 2CSP constraint on (if it exists), the assignment satisfies the constraint.

Notice that the size of our reduction (number of vertices of Gψ)is .

Completeness. If OPT(ψ) = 1, then Gψ has a k-clique: Fix a satisfying assignment for ψ, and let S be the set of all vertices that are consistent with this assignment. Notice that . Furthermore, its vertices do not violate any consistency constraints (since they agree with a single assignment) or 2CSP constraints (since we started from a satisfying assignment).

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.