Exercises

Search in book...
Toggle Font Controls
Create new playlist

Name your new playlist

Playlist description (optional)
Sign In

Email address

Password

Forgot Password?

or

Continue with Facebook

Continue with Google
Sign Up

Full Name

Email address

Confirm Email Address

Password

or

Continue with Facebook

Continue with Google

Example 11.33

Proof

For b ≤ 3, the theorem is trivial. In the following, we construct an L-reduction from VC-b, with b ≥ 4, to VC-3. Given a graph $c11-math-1726$ in which every vertex has degree at most b, we construct a graph G^′ as follows: For each vertex x of degree d inG, construct a path p_x of $c11-math-1733$ vertices to replace it as shown in Figure 11.2. Note that this path has a unique minimum vertex cover c_x with size d − 1. This vertex cover covers only edges in path p_x. The set $c11-math-1737$ of vertices in p_x but not in c_x is also a vertex cover of p_x. This vertex cover has size d but it covers all edges in p_x plus all edges that are originally incident on x and now incident on path p_x.

Assume that $c11-math-1745$ and $c11-math-1746$ . For any vertex cover S of graph G, the set

is a vertex cover of $c11-math-1750$ . In addition, if S is of size s, then the size of S^′ is $c11-math-1754$ . (Note that the set $c11-math-1755$ has size 2m.)

Conversely, for each vertex cover S^′ of $c11-math-1758$ , the set

is a vertex cover of G. Furthermore, if $c11-math-1761$ and $c11-math-1762$ , then $c11-math-1763$ .

One immediate consequence from the above relation is that

where $c11-math-1765$ denotes the minimum size of vertex covers for G. Note that $c11-math-1767$ . Thus, we have

that is, condition (L1) holds for this reduction. Also note that $c11-math-1769$ is equivalent to

So, condition (L2) also holds. Therefore, this reduction is an L-reduction.

Example 11.34

Proof

The following property of L-reduction shows the precise relation between the corresponding approximation problems. (Recall the definition of r-APPROX-Π from Section 2.5.)

Proposition 11.35

Proof

From Proposition 11.35, we have the following relations:

Assume that Π is a minimization problem. If $c11-math-1858$ and Γ has a polynomial-time linear approximation algorithm (meaning that the approximation ratio r is a constant), then Π also has a polynomial-time linear approximation algorithm.
If $c11-math-1862$ and Γ has a (fully) polynomial-time approximation scheme, then Π has a (fully, respectively) polynomial-time approximation scheme.

We know from Corollary 11.28 that there exists a number s > 1 such that the problem s-APPROX-3SAT is $c11-math-1867$ -hard for NP. The L-reduction can pass this inapproximability result from 3-SAT to other problems. We first consider the following restricted version of 3-SAT, which is a fundamental problem for proving inapproximability results.

3SAT-3: Given a 3-CNF formula⁶

F in which each variable appears in at most three clauses, find a Boolean assignment to the variables of F to maximize the number of true clauses.

We are going to show that $c11-math-1871$ S $c11-math-1872$ -3. To prove this, we need a combinatorial lemma involving expanders. Recall that a d-regular graph $c11-math-1874$ is an expander if

for some constant δ > 0. From Lemma11.9, we know that there is a family $c11-math-1877$ of d₀-regular expanders of n vertices that have $c11-math-1880$ , where d₀ and $c11-math-1882$ are global constants. In other words, for any $c11-math-1883$ , with $c11-math-1884$ , $c11-math-1885$ . We now prove a lemma using these expander graphs as a tool.

**Figure 11.3** Trees for fan-out, where the open circles denote new vertices.

Lemma 11.36

Proof

Assume that $c11-math-1903$ . Construct $c11-math-1904$ copies of X_n. Call them $c11-math-1906$ , with the vertices in H_j being $c11-math-1908$ , for $c11-math-1909$ . Next, for each $c11-math-1910$ , define a binary tree T_i such that its leaves are exactly the set $c11-math-1912$ (and the internal nodes of T_i are new vertices, occurring only in T_i). Connect the root of T_i with x_i for each $c11-math-1917$ . Call the resulting graph $c11-math-1918$ . It is obvious that W is connected. Note that each node in Y has degree at most $c11-math-1921$ and each $c11-math-1922$ has degree 1.

Next, we change W into a digraph $c11-math-1924$ by replacing each edge $c11-math-1925$ in F by two edges (u,v) and (v,u). Finally, foreach node y in $c11-math-1930$ , we perform the following degree-reducing operation on it: If y has out-degree d ≥ 2, then replace the d out-edges by a tree as shown in Figure 11.3(a), and if y has in-degree d ≥ 2, then replace the d in-edges by a tree as shown in Figure 11.3(b). Let the resulting digraph be $c11-math-1937$ , and let $c11-math-1938$ , $c11-math-1939$ , be the subgraph resulting from the above degree-reducing operation performed on vertices in H_j. Note that $c11-math-1941$ for all $c11-math-1942$ .

We now verify that G satisfies our requirements.

: The set Y has n vertices from X, n trees T_i each of size $c11-math-1949$ . (All vertices in H_j, $c11-math-1951$ , are the leaves of these trees.) Therefore, $c11-math-1952$ . Each vertex in W has degree at most $c11-math-1954$ , and so, each vertex in W^′ has in-degree at most $c11-math-1956$ and out-degree at most $c11-math-1957$ . Therefore, from W^′ to G, we added, for each vertex in Y, at most $c11-math-1961$ more vertices. So, the total number of vertices in V is $c11-math-1963$ . Note that t and d₀ are absolute constants.
: This part is obvious from the construction.
: First, for any , we claim that for any , with , we have

From the property of the expander X_n, we know that, in $c11-math-1971$ , it is true that

Now, when we perform the degree-reducing operation on any $c11-math-1973$ , we reduce at most $c11-math-1974$ edges from $c11-math-1975$ to $c11-math-1976$ to one edge from S_j to $c11-math-1978$ . To see this, we first consider the operation of Figure 11.3(a) on a vertex $c11-math-1979$ . Assume that $c11-math-1980$ and that at least one of its out-neighbors is not in S_j. Then, there are two cases:
1. All newly created vertices (the open-circle vertices) are in S_j. Then, the number of edges from S_j to $c11-math-1984$ is unchanged.
2. At least one of the newly created vertices is not in S_j. Then, there is at least one edge from S_j to $c11-math-1987$ that ends in a vertex in $c11-math-1988$ . In this case, the number of edges decreases at most by a factor of 1/(d₀ + 1).
Next, we perform the operation of Figure 11.3(b) on all vertices in H_j. We note that only those edges created in Case (1) above are affected and, again, the number of these edges decreases at most by a factor of 1/(d₀ + 1). In other words, each original edge only participates in one of the two operations. So, we have

and the claim is proven.

As the digraph W^′ is symmetric, the assumption of the claim also implies that

Now, let $c11-math-1993$ have $c11-math-1994$ . For each $c11-math-1995$ , let $c11-math-1996$ , and

Case 1. $c11-math-1998$ . Then, for each $c11-math-1999$ , the above claim shows that $c11-math-2000$ , and so

Case 2. $c11-math-2002$ . For any x_i,j in H_j, $c11-math-2005$ and $c11-math-2006$ , if $c11-math-2007$ =1, then we say x_i,j is inconsistent (with x_i). Note that if x_i,j is inconsistent, then there must exist an edge in the tree T_i that is in $c11-math-2013$ . Assume that for some fixed j, $c11-math-2015$ (or $c11-math-2016$ ). Then, there must be $c11-math-2017$ vertices in H_j that are inconsistent, because $c11-math-2019$ . So, there are at least $c11-math-2020$ edges between S and $c11-math-2022$ in the trees $c11-math-2023$ . Together, we get

From the above two cases, we get $c11-math-2025$ . As the digraph G is symmetric, it follows that $c11-math-2027$ too. This completes the proof of condition (c).

Theorem 11.37

Proof

We will construct an L-reduction from 3SAT to 3SAT-3. Let F be a given 3-CNF formula. For each variable x with k ≥ 4 occurrences in F, we replace the occurrences of x by k new variables $c11-math-2038$ , The idea, then, is to add a linear number of new clauses of the form $c11-math-2039$ such that, in order to maximize the number of true clauses, it does not pay to assign different values to $c11-math-2040$ . (Note also that each x_i can occur in at most two new clauses.) To do this, we construct the directed graph $c11-math-2042$ for $c11-math-2043$ as in Lemma 11.36. Treat all vertices in $c11-math-2044$ as new Boolean variables and, for each edge $c11-math-2045$ , add a new clause $c11-math-2046$ (i.e., $c11-math-2047$ ) to the formula. We do this for each variable x and let h(F) be the resulting formula. By condition (b) of Lemma 11.36, each variable occurs at most three times in h(F) and, hence, h(F) is an instance of 3SAT-3. We now show that h(F) has an interesting property that for any Boolean assignment τ, there exists an assignment $c11-math-2054$ such that

The number of clauses satisfied by $c11-math-2055$ is no smaller than the number of clauses satisfied by τ; and
All those variables $c11-math-2057$ introduced from the same variable x take the same value in $c11-math-2059$ .

In fact, if τ does not satisfy property (2) with respect to variables in $c11-math-2061$ , then we can assign all variables y in V_x the majority value of $c11-math-2064$ as $c11-math-2065$ . Let $c11-math-2066$ . We observe that the change from τ to $c11-math-2068$ may turn at most $c11-math-2069$ satisfying clauses in F to unsatisfying. However, by Lemma 11.36, it also increases at least $c11-math-2071$ satisfying clauses corresponding to edges in G_x. Let $c11-math-2073$ be the Boolean assignment for F that assigns each variable x of F with the value taken by the corresponding variables in G_x under assignment $c11-math-2078$ . Note that if F has m clauses, then h(F) has at most $c11-math-2082$ variables, where c is the constant of Lemma 11.36. Also, each variable occurs in at most three clauses. It follows that h(F) has at most $c11-math-2085$ clauses (note that each clause has at least two literals). From the fact that 2-APPROX-3SAT is polynomial-time solvable (see Exercise 11.16), we have

That is, condition (L1) holds. Also, from the properties (1) and (2) of $c11-math-2087$ , we have

where $c11-math-2089$ (and $c11-math-2090$ ) is the number of satisfying clauses in F (and h(F)) under the assignment $c11-math-2093$ (and τ, respectively). So, condition (L2) also holds.

Theorem 11.38

Proof

There is a big class of approximation problems that can be proved to be NP-hard using the L-reduction. The following is another example.

VC-IN-CUBIC-GRAPHS (VC-CG): Given a graph G in which every vertex has degree exactly 3 (called a cubic graph), find the minimum vertex cover of G.

Theorem 11.39

Proof

We construct an L-reduction from VC-3 to VC-CG. Let G be an instance of VC-3, that is, a graph in which every vertex has degree at most 3. Suppose that G has i vertices of degree 1 and j vertices of degree 2. We construct $c11-math-2113$ triangles and a cycle of size $c11-math-2114$ and connect two vertices of each triangle to two adjacent vertices of the cycle (see Figure 11.4). Denote this graph by H. Call, in each triangle, the vertex that is not connected to the cycle a free vertex in H. Note that H has a minimum vertex cover of size $c11-math-2118$ (the cycle needs $c11-math-2119$ vertices to cover and each triangle needs two vertices to cover) and there exists a minimum vertex cover of H containing all free vertices.

Now, we construct graph G^′ from G and H as follows: For each vertex x of degree 1 in G, connect x to two free vertices; and for each vertex x of degree 2 in G, connect x to one free vertex. Thus, each free vertex is adjacent to exactly one vertex in G. Clearly, G has a vertex cover of size s if and only if G^′ has a vertex cover of size $c11-math-2134$ . Therefore,

Note that G has at least $c11-math-2137$ edges and each vertex in G can cover at most three edges. Therefore, $c11-math-2139$ and, hence, $c11-math-2140$ . It follows that

and condition (L1) holds. To prove (L2), we note that for each vertex cover S^′ of size s^′ in $c11-math-2144$ , we can obtain a vertex cover S of size $c11-math-2146$ in G by simply removing all vertices in S^′ that are not in G. It follows that

Therefore, (L2) also holds.

In Section 2.5, we divided the optimization problems into three classes, according to their approximability. The third class contains the problems with polynomial-time approximation schemes. The second class contains the problems for each of which there is a constant $c11-math-2151$ such that it is polynomial-time approximable with respect to ratio r₀ but is inapproximable in polynomial time for any ratio $c11-math-2153$ unless $c11-math-2154$ . We just showed that the maximum satisfiability belongs to this class. As L-reductions preserve linear-ratio approximation, all problems that are L-equivalent to 3-SAT belong to this class, including the problems VC-3, IS-3, 3SAT-3, and VC-CG studied above (cf. Exercise 11.16).

Next, we turn our attention to problems in the first class, the class of problems for which the corresponding approximation problems are NP-hard for all ratios r > 1. In the last section, we saw that the problem CLIQUE belongs to this class. We can actually further divide this class into subclasses according to the best approximation ratio r(n), where r(n) is a function of input size n. For instance, consider the following problem:

SET COVER (SC): Given a finite collection $c11-math-2161$ of subsets of a set U of m elements, find a minimum cardinality subcollection of $c11-math-2164$ such that the union of all subsets in the subcollection covers U.

It is known that SC has a polynomial-time approximation algorithm with approximation ratio $c11-math-2166$ . In fact, this is the best-known result unless NP collapses to a deterministic subexponential time class.

Theorem 11.40

Proof

Note that both the problems SC and CLIQUE belong to the first class of inapproximable optimization problems, but they still have different approximation ratios: CLIQUE is so hard to approximate that it is not approximable in polynomial time within ratio $c11-math-2170$ for any ε > 0 (if $c11-math-2172$ ), but SC has a polynomial-time approximation algorithm to achieve the approximation ratio $c11-math-2173$ .

The problem SC is a fundamental problem for classifying optimization problems to the first class. We show an application below.

SUBSET INTERCONNECTION DESIGNS (SID): Given a complete weighted graph H on vertex set X and given subsets $c11-math-2176$ of X, find a minimum-weight subgraph G (called a feasible subgraph) of H such that for every $c11-math-2180$ , G contains a spanning tree for X_i.

Theorem 11.41

Proof

We reduce the problem SC to SID as follows: For each instance $c11-math-2186$ of SC, assume that $c11-math-2187$ and $c11-math-2188$ . We construct an instance $c11-math-2189$ of SID by setting

and assigning weights on edges as follows:

where $c11-math-2192$ .

For each set cover $c11-math-2193$ of $c11-math-2194$ , we can construct a feasible subgraph G of H by connecting edges $c11-math-2197$ to the complete graph on vertices 1, $c11-math-2198$ , n. This subgraph G has total weight $c11-math-2201$ . If the optimal solution for the instance $c11-math-2202$ of SC is a subcollection of s^∗ sets, then the minimum feasible subgraph for H has totalweight between s^∗ and $c11-math-2206$ .

Conversely, if G is a feasible subgraph of $c11-math-2208$ with total weight c(G), then the set

is a set cover of U and

Now, suppose that there exists a polynomial-time approximation algorithm for SID with approximation ratio $c11-math-2213$ for some $c11-math-2214$ . We compute an approximate solution for an instance $c11-math-2215$ of the problem SC as follows:

Step 1. Check all subcollections of $c11-math-2216$ of size at most 1/(2(1 − ρ). If there exists a set cover of U among them, then choose the one with the minimum cardinality as solution; else, go to step 2.Step 2. Construct an instance $c11-math-2218$ of SID from $c11-math-2219$ . Use the polynomial-time approximation algorithm for SID to find a feasible subgraph G of $c11-math-2221$ . Define $c11-math-2222$ as the approximate solution to the instance $c11-math-2223$ .

Clearly, if the solution comes from step 1, then it is optimal; if the solution comes from step 2, then the optimal solution of $c11-math-2224$ must have size $c11-math-2225$ , or, equivalently, $c11-math-2226$ . Therefore, we have

That is, this approximate solution is within a factor of $c11-math-2228$ from the optimal, where $c11-math-2229$ . By Theorem 11.40, $c11-math-2230$ .

Exercises

11.1 Show that co-RP = PCP $c11-math-2231$ .

11.2 Show that there exists a constant $c11-math-2232$ such that for every Boolean function f with q variables, there exists a 3-CNF formula F with $c11-math-2236$ clauses such that f is satisfiable if and only if F is satisfiable.

11.3 For each 3-CNF Boolean formula F, construct a constraint graph G_F such that F is satisfiable if and only if G_F is satisfiable.

11.4 Show that for d-regular graph G, $c11-math-2245$ .

11.5 Consider a d-regular graph $c11-math-2247$ . Show that for all $c11-math-2248$ ,

11.6 Prove Lemma 11.14.

11.7 Prove Lemma 11.15.

11.8 Show that two different linear functions from $c11-math-2250$ to {0,1} differ in exactly a fraction 1/2 of locations.

11.9 Show Parseval's Identity used in the proof of Theorem 11.21.

11.10 Show that if for every Boolean function $c11-math-2252$ , there exist q Boolean functions $c11-math-2254$ , ..., $c11-math-2255$ such that f is satisfiable if and only if $c11-math-2257$ is satisfiable, then $c11-math-2258$ .

11.11 Show that for every Boolean function $c11-math-2259$ , there exist an alphabet $c11-math-2260$ and q functions $c11-math-2262$ , ..., $c11-math-2263$ from $c11-math-2264$ to {0,1} such that f is satisfiable if and only if $c11-math-2267$ is satisfiable.

11.12 The goal of steps (3) and (4) of the assignment testing proof system of Section 11.2.3 is to verify that a satisfies Ψ. Why cannot we just verify this by testing directly whether, for a random $c11-math-2270$ , $c11-math-2271$ ?

11.13 (Multiple Prover Interactive Proof Systems). We extend the formulation of the interactive proof systems of Exercise 10.1 to multi-prover interactive proof systems in which more than one provers work together to convince the verifier that the input x is in the language L. To make it more powerful than the one-prover systems, the provers in a multi-prover system are not allowed to communicate with each other, once the proof system is activated. Formally, let $c11-math-2274$ be k DTMs and M_v be a polynomial-time PTM. We say $c11-math-2277$ is a k-prover interactive protocol if they share a common read-only tape and for each i, $c11-math-2280$ , $c11-math-2281$ and M_v share a communication tape T_i, and they compute in the same manner as the one-prover interactive protocol. That is, M_v and one of $c11-math-2285$ , $c11-math-2286$ , take turns in being active. Suppose M_v is activated by $c11-math-2288$ ; then it reads the string on tape T_i, computes a string y and an integer j, $c11-math-2292$ , and then writes the string y on tape T_j and activates machine $c11-math-2295$ (or it may choose to halt and accept or reject). The activity of a prover $c11-math-2296$ is similar, except that it can only read from and write to tape T_i, that is, M_i cannot access tape T_j if $c11-math-2300$ . We say that a set $c11-math-2301$ has a k-prover interactive proof system with error bound ε if there exists a PTM M_v such that the following hold:

There exist k DTMs $c11-math-2306$ , $c11-math-2307$ , $c11-math-2308$ such that $c11-math-2309$ , $c11-math-2310$ , $c11-math-2311$ , $c11-math-2312$ forms a k-prover interactive protocol and for each $c11-math-2314$ , the probability of these k + 1 machines together accepting x is at least $c11-math-2317$ ; and
For any k DTMs $c11-math-2319$ such that $c11-math-2320$ forms a k-prover interactive protocol and for any $c11-math-2322$ , the probability of these k + 1 machines together accepting x is at most ε.

Extend the above definition to allow the number k of provers being a function depending on the input size $c11-math-2327$ . Show that if a set L is in $c11-math-2329$ , then L has a k(n)-prover interactive proof system with error bound 1/4 for some polynomial function k.
Prove that if L has a k(n)-prover interactive proof system with error bound 1/4 for some polynomial function k, then L has a two-prover interactive proof system with error bound 1/4.
Show that if L has a two-prover interactive proof system with error bound 1/4, then $c11-math-2338$ .

11.14 Show that $c11-math-2339$ .

11.15 Extend the PCP characterization of NP to PSPACE and $c11-math-2340$ .

11.16 Show that the problems 2APPROX-3SAT, 2-APPROX-VC-3, and 4-APPROX-IS-3 are solvable in polynomial time.

11.17 Show that if $c11-math-2341$ , then the problem r-APPROX-CLIQUE is not polynomial-time solvable with ratio $c11-math-2343$ for all ε > 0.

11.18 Consider the problem 2SAT-4: Given a 2-CNF formula in which each variable occurs at most four times, find a Boolean assignment to maximize the number of satisfying clauses. Show that there exists a real number r > 1 such that r-APPROX-2SAT-4 is $c11-math-2347$ -hard for NP.

11.19 Consider the problem STEINER MINIMUM TREES-IN-GRAPH (SMT-G): Given an edge-weighted graph G and a vertex subset S, find a minimum-weight subgraph interconnecting vertices in S. Show that there exists a real number r > 1 such that r-APPROX-SMT-G is $c11-math-2354$ -hard for NP.

11.20 Consider the problem SMT-IN-DIGRAPH (SMT-DG): Given an edge-weighted directed graph G, a vertex x, and a vertex subset S, find a minimum-weight directed tree rooted at x and connected to every vertex in S. Show that

For some ρ > 0, there is no polynomial-time approximation algorithm with the approximation ratio $c11-math-2362$ for SMT-DG unless $c11-math-2363$ ; and
For any ε > 0, there exists a polynomial-time approximation algorithm for SMT-DG with the approximation ratio n^ε.

11.21 Consider the problem LONGEST PATH (LP): Given a graph G and two vertices x and y in G, find the longest path between x and y in G. For any graph $c11-math-2373$ , let G² be the graph with vertex set $c11-math-2375$ and edge set $c11-math-2376$ . Prove that there exists a path of length k between two vertices x and y in G if and only if there exists a path of length k² between (x,x) and(y,y) in G². Use this fact to find the best approximation ratio of any polynomial-time approximation algorithm for LP.

11.22 Show that 3-SAT is L-reducible to TSP with the triangle inequality.

11.23 Recall the problem SHORTEST COMMON SUPERSTRING (SCS) of Exercise 2.20(c). Show that 3-SAT is L-reducible to SCS.

11.24 Consider the problem MIN-BISECTION: Given a graph G, divide G into two equal halves to minimize the number of edges between the two parts. Study the approximability of this problem.

11.25 Show that the following problems have no polynomial-time approximation with approximation ratio $c11-math-2389$ for $c11-math-2390$ unless $c11-math-2391$ :

Given a finite collection $c11-math-2392$ of subsets of a set U of m elements, find a minimum subset intersecting every subset in $c11-math-2395$ .
Given a finite collection $c11-math-2396$ of subsets of a set U of m elements, find a minimum cardinality subcollection of $c11-math-2399$ such that all subsets in the subcollection are disjoint and the union of all subsets in the subcollection covers U.

11.26 Show that for each of the following problems, there exists a real number $c11-math-2401$ such that the problem has no polynomial-time approximation with approximation ratio $c11-math-2402$ unless $c11-math-2403$ :

LP (defined above in Exercise 11.21).
Given a system of n linear equations in m variables $c11-math-2406$ with integer coefficients and $c11-math-2407$ , find the minimum number of equations such that removal of them makes the remaining system feasible (in the sense that the system has at least one solution).

11.27 An optimization problem Π is A-reducible to an optimization problem Γ if there exist three polynomial-time computable functions h,g, and c such that (i) for any instance x of Π, h(x) is an instance of Γ; (ii) for any solution y to h(x), $c11-math-2419$ is a solution to x; and (iii) if the error ratio of y to h(x) is bounded by e, then the error ratio of $c11-math-2424$ to x is bounded by c(e), where the error ratio of a solution z to an instance x is $c11-math-2429$ . Prove that if Π is A-reducible to Γ and Γ is approximable in polynomial time with ratio r(n), then Π is approximable in polynomial time with ratio $c11-math-2436$ .

Historical Notes

The celebrated result of the PCP characterization of NP started with the extension of the notion of interactive proof systems to the multi-prover proof systems (see Exercise 11.13) by Ben-Or et al. (1988). They defined MIP as the class of languages accepted by a multi-prover proof system in polynomial time. Fortnow et al. (1994) presented an equivalent formulation of the class MIP, based on the notion of randomized oracle TMs. Babai, Fortnow, and Lund (1991) showed that MIP = NEXPPOLY. Babai, Fortnow, Levin and Szegedy (1991) and Feige et al. (1996) further improved this result on problems in NP. Particularly, Feige et al. (1996) introduced a new notion of nonadaptive proof systems with restrictions on the number of random bits used and the number of queries asked by the verifier. Arora and Safra (1992, 1998) generalized it and called it the probabilistically checkable proof (PCP) system. They also introduced the idea of composing two proof systems into one and showed that $c11-math-2437$ . The final characterization of $c11-math-2438$ (Theorem 11.4) was proved by Arora et al. (1992, 1998). A complete proof along above line can be found in Arora's (1994) Ph.D. thesis (also in the first edition of this book).

An important idea in the above development is to encode the proofs by some error-correcting coding scheme. For a complete treatment of the coding theory, see, for instance, Berlekamp (1968) and Roman (1992). The application of error-correcting coding to program checking has been studied by Blum and Kannan (1989), Blum, Luby, and Rubinfeld (1990), Gemmell et al. (1991), Lipton (1991), and Rubinfeld and Sudan (1996).

Our presentation of the proof of the PCP theorem follows from a short one given by Dinur (2007). This short proof uses the close relationship between the PCP theorem and approximation algorithms. For the general study of expander graphs and their applications to computer science, see Chapter 9 of Alon and Spencer (2011) and Hoory et al. (2006). The assignment tester has been studied in Dinur and Reingold (2006). The BLR test is from Blum, Luby, and Rubinfeld (1990). Radhakrishnan (2006) and Radhakrishnan and Sudan (2007) contain simplified proof of the graph powering step of Dinur's proof.

The study of approximation algorithms for optimization problems has been around for more than 30 years (see, e.g., Graham (1966) and Garey et al. (1972)). While a number of approximation algorithms have been found, the progress on negative results was slow before the 1990s. The first important work on inapproximability was given by Papadimitriou and Yannakakis (1991). They defined a class MAX-SNP that contains many NP-hard optimization problems that have polynomial-time linear approximation algorithms. They also studied complete problems for MAX-SNP under the L-reduction and showed that if any one of these problems has a polynomial-time approximation scheme, then every problem in MAX-SNP has a polynomial-time approximation scheme. The MAX-SNP-hardness was then widely used to establish the inapproximability results (see, e.g., Bern and Plassmann (1989)). In addition to the L-reduction, similar reductions, such as the A-reduction (Crescenzi and Panconesi, 1991) and AP-reduction (Crescenzi et al., 1995), have been proposed to prove inapproximability results. However, all these results relied upon the unproved assumption that r-APPROX-3SAT is not in P for some r > 1.

The breakthrough came in 1991, when Feige discovered the connection between the multi-prover proof systems of NP and approximability of the problem CLIQUE (see Feige et al. (1991, 1996); also see Condon (1993)). Following this piece of work and the PCP characterization of NP, the inapproximability results mushroomed. Arora et al. (1992, 1998) established that 3-SAT is inapproximable in polynomial time for some constant ratio r > 1 and, hence, all MAX-SNP-hard problems are inapproximable for some constant ratio. The best ratio 8/7 for the maximum 3-SAT problem was found by Hastad (1997) and Karloff and Zwick (1997). The problem VC-4 was shown to be one of the MAX-SNP-complete problems in Papadimitriou and Yannakakis (1991). Our result on VC-3 (Theorem 11.38) is from Du et al. (1998). Lund and Yannakakis (1994) built some new PCP systems to prove the inapproximability of problems beyond the class MAX-SNP, including the problem SET COVER. The optimum ratio $c11-math-2446$ for SET COVER in Theorem 11.40 was obtained by Feige (1996). Other results in this direction include Arora and Lund (1996), Bellare et al. (1993),Raz and Safra (1997), and Du et al. (1998). The hardest approximation problems belong to the maximum clique problem and the minimum chromatic number problem, which are known to be inapproximable with respect to ratio $c11-math-2447$ for any ε > 0 (Feige and Killian, 1996; Hastad, 1996). These inapproximability results also motivated some positive results. Among them, Arora (1996) proved that TSP on the Euclidean plane has a polynomial approximation scheme (see also Mitchell (1999)). Arora (1998) contains a survey of inapproximable results. Condon et al. (1993) and Kiwi et al. (1994) extended the PCP characterizations to classes PSPACE and PH. These papers and that by Ko and Lin (1995a, 1995b) also contain inapproximability results on optimization problems in PSPACE and PH.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.

Table of Contents for Exercises

Create new playlist

Sign In

Sign Up

Example 11.33

Proof

Example 11.34

Proof

Proposition 11.35

Proof

Lemma 11.36

Proof

Theorem 11.37

Proof

Theorem 11.38

Proof

Theorem 11.39

Proof

Theorem 11.40

Proof

Theorem 11.41

Proof

Exercises

Historical Notes

Table of Contents for
Exercises