Mayr E.W., Pr?mel H.J., Steger A. (eds.) Lectures on Proof Verification and Approximation Algorithms

Подождите немного. Документ загружается.

8.2. Constraint Satisfaction Problems 215

class reduces to a gap problem GAP-IIc,,. The second step was straightforward

in the last chapter: The computations of the verifiers were in one to one cor-

respondence to instances of MAXE3SAT and MAXLINEQ3-2, respectively. The

completeness and the soundness of the verifiers serve as thresholds for the cor-

responding gap problems.

Once we have identified an A/P-hard gap problem we can try to design reductions

to other problems which preserve the gap within certain limits. We define a

gap-

preserving

reduction between optimization problems as a reduction between the

corresponding gap problems:

Definition 8.1 (gap-preserving reduction [AL96]).

Let H and H' be two

maximization problems. A

gap-preserving reduction

from II to H ~ with parame-

ters (c, s) and (c', s') is a polynomial time algorithm f that satisfies the following

properties:

- for every instance I of II, algorithm f produces an instance I' = f(I) of H',

- Opt(I)/lI I >1 c ~ Opt(I')/lI'l >1 c',

- Opt(I)/[I[ < s ~ Opt(I')/[I'[ < #.

Lemma 8.2.

Given a gap-preserving reduction from II to II ~ with parameters

(c, s) and (c', s'), AfTa-hardness of

GAP-IIc,s

implies that achieving an approxi-

mation ratio cl/s ' is ~rTa-hard for H ~.

In the previous example we saw how to construct a gap-preserving reduction

using a gadget. Gadgets suitable for deriving non-approximability results must

meet some structural requirements. The following sections show how for a re-

stricted class of problems, the notion of a gadget can be formalized, how its

performance can be measured, and how optimal gadgets can be constructed

using a computer.

8.2 Constraint Satisfaction Problems

Usually non-approximability results have been improved by constructing new

PCP verifiers optimizing the query complexity, the soundness or other param-

eters of the proof systems (see Chapters 4.6 and 4.7 for a discussion on the

developments concerning the clique problem). Such a clear interaction between

the parameters of a proof system and the approximation ratio which is hard to

achieve is not available for APX-problems in general [Bel96]. A further improve-

ment in recent PCP verifiers, especially in [BGS95] and in [H&s97b], has been

the fact that the way in which a particular verifier accepted or rejected on the

basis of the answers to the queries was made explicit and could be expressed by

simple Boolean functions.

216 Chapter 8. Deriving Non-Approximability Results by Reductions

Theorem 8.3. [Hds97b] For any e, ~ > 0 there is a verifier V for ROBE3SAT,

which

uses O(logn) random bits

has completeness 1 - r and soundness

reads exactly three bits from the proof and accepts iff the exclusive or of the

three bits matches a value, which depends only on the input and the random

string.

This led Trevisan et al. [TSSW96, Tre97] to generalize the MAXSAT problem

to "constraint satisfaction" problems. In a constraint satisfaction problem, ar-

bitrary Boolean functions, called constraints, take the r61e of the clauses in

MAXSAT. An instance of a constraint satisfaction problem becomes a collection

of constraints and the goal is to maximize the number of satisfied constraints,

i.e., to find an assignment to the Boolean variables such that a maximum number

of constraints evaluate to TRUE. Restrictions in the choice of Boolean functions

define different constraint satisfaction problems.

For a verifier from Theorem 8.3 we can associate a constraint with each random

string of the verifier. These constraints are parity checks. If x E L then a fraction

of c (the completeness of the verifier) of the constraints is satisfiable. If x r L

then a fraction less than s (soundness of the verifier) of the constraints are

satisfiable.

Definition 8.4 (constraint function).

Boolean function f: {0, 1} k ~ {0, 1}.

A (k-ary) constraint function is a

Definition 8.5 (constraint).

A constraint C over a variable set { X1, . . . , X~ }

is a pair C = (f, (il,...,ik)) where f : {0, 1} k --~ {0, 1} is a constraint function

and ij E [n] for j E [k]. Variable Xj is said to occur in C if j E {Q,...,ik}.

All variables occuring in C are different. The constraint C is satisfied by an

assignment if= al,...,an to X1,...,Xn if C(al,...,an) := f(aix,... ,ai~) = 1.

Definition 8.6 (constraint

family). A constraint family fir is a finite collec-

tion of constraint functions. We say that constraint C is from fir if f E fir.

Example 8.7. We give a number of constraint families that will be used sub-

sequently.

- Parity check is the constraint family PC = {PCo, PC1}, where, for i e {0, 1},

PCi is defined as follows:

1 ifa@b~c=i

PCi( a, b, c) = 0 otherwise

Note that PC is the constraint family for encoding the operation of the type

of verifier of Theorem 8.3.

8.3. The Quality of Gadgets 217

- Exactly-k-SAT is the constraint family EkSAT = {f : {0, 1} k -+ {0, 1} : J{~ :

f(g) = 0}J = 1}

- k-SAT is the constraint family kShT ---- UlE[k] E/SAT

- CUT is the constraint function CUT : {0, 1} 2 -+ {0, 1} with CUT(a, b) = a@b

- DICuT is the constraint function DICUT : {0, 1} 2 -~ {0, 1} with CUT(a, b) =

-~a A b

A constraint satisfaction problem can now be stated as

MAX ~"

Instance: Given a collection [C1, C2,..., C,~] of constraints from a constraint

family ~" on n variables

Problem: Find an assignment to the variables which maximizes the number of

satisfied constraints.

Note that we allow the same constraint to occur several times in an instance of a

constraint satisfaction problem and that MAxPC is equivalent to MAxLINEQ3-

2. The computation of a verifier from Theorem 8.3 can be expressed as an in-

stance of MAxPC. If the instance of ROBE3SAT is satisfiable then a fraction of

1 - e of the constraints are satisfiable. Otherwise a fraction of at most ~ of

the constraints are satisfiable. This establishes a gap-preserving reduction from

ROBE3SAT to Gap-MAxPC 1 ,,~__+A. By Lemma 8.2 it is hard to approximate

-- 2

MAxPC to within 2 - ~.

8.3 The Quality of Gadgets

In order to obtain hardness results for other constraint satisfaction problems our

aim is now to develop gap-preserving reductions from MAxPC to the problem

of interest. This section explains how gadgets can be used to construct such

reductions and how the "quality" of the gadgets affects the preserved gap. We

start by defining a first type of gadget.

Definition 8.8 ((~,/~)-gadget). For (~, j3 E N + , a constraint function

J' : {0,1} k -~ {0,1}, and a constraint family Jr:

an (a, f~)-gadget reducing f to Jr is a finite collection r = [C1, C2,..., Cm] of

constraints from :7: over primary variables X1,..., Xk and auxiliary variables

Y1,..-, Yn, with the property that for Boolean assignments ~ to X1,..., Xk and

to Y1,..., Yn the following relations are satisfied:

218 Chapter 8. Deriving Non-Approximability Results by Reductions

(v~: f(a) = 1)(v~): ~c~(~,~) ~< ~ (8.1)

(Vg: f(~) = 1)(3b): ~-~Cj(~,b) = a (8.2)

(v~: I(~) =o)(v~):Zc~(~,~)

~< ~-~.

(8.3/

The gadget is called strict if, in addition,

(v~: f(~) =01(3~): ~cj(~,~) = ~-~. (8.4/

Remark 8.9.

- Our introductory reduction from 3SAT to MAX2SAT is a (7, 1)-gadget.

- The notion of strictness is not important to prove non-approximability; how-

ever, strict gadgets have applications in the construction of approximation

algorithms (see Exercise 8.3).

A gadget may be thought of as an instance of the constraint satisfaction problem

which is the target of the reduction. With respect to a reduction from a constraint

function f, a gadget has the property that when restricted to any satisfying

assignment ~ to X1,... ,Xk its maximum is exactly a, and when restricted to

any unsatisfying assignment its maximum is at most c~ -/~. This means that

there is a gap in the number of constraints that are satisfiable in these two

cases. The fraction ~ is a characteristic value for the quality of a gadget with

respect to the gap-preserving reduction in which it is used. The smaller this

fraction, the better the gap preserved by the reduction, i.e., the stronger the

obtained non-approximability result. This interaction will be made explicit in

Theorem 8.13. If our source problem of the reduction consists only of instances

formed by constraints from a single constraint function f, we can immediately

state the following

Lemma 8.10. Let e and s E (0, 1). An (~, ~)-gadget reducing :To = (f) to a

constraint family .T yields a gap-preserving reduction from MAX.To to MAX.T

with parameters (c, s) and (c', s'), where c* and s' are constants satisfying

C t COt

s -7/> ~ - (1 - s)/~"

Proof. Assume that the instance from ~'0 = (f} consists of m constraints (our

source). The gadget produces an instance from ~" (our target). Let ~ be the total

number of constraints in a gadget used to replace each constraints of the source.

In order to prove the claimed gap, we first need a lower bound on the number of

8.3. The Quality of Gadgets 219

constraints that is satisfiable in the target when more than cm constraints are

satisfied in the source. From (8.2) we can conclude that

6~n~

c'/> Ira"

On the other hand we need an upper bound when less than sm constraints are

satisfied in the source. In this case, the error introduced by the gadget contributes

m(a -/3) satisfiable target constraints; for each satisfiable source constraint, we

get/3 more satisfiable target constraints, i.e.,

m(a - t3) + stuff

s ~

Note that (8.1) and (8.3) are necessary here to get the desired upper bound. 9

What happens if our "source" problem is made up from constraint families with

more than one constraint function, like PC= {PCo,PC1}? For ~" = Uz f~ and

weights wi E Q+, ~'~i wi = 1, we define

WMAx 3 u

Instance: Given ra constraints from a constraint family ~ = Ui fi on n vari-

ables so that mwi constraints are from fi-

Problem: Find an assignment to the variables which maximizes the number of

satisfied constraints.

For notational convenience, the following lemma, which is a generalization of

Lemma 8.10, is only formulated for the case of Yo = {fl, f2}.

Lemma 8.11. Let 5to = {fl,f2} be a constraint family and let wl,w2 E Q+,

Wl + w2 = 1, at, a2,13 E N, al <~ a2. Let Y: be a constraint family. If there exist

an (al, ~)-gadget reducing fl to 9 c and an (a2, ~)-gadget reducing f2 to Y: then,

for any c >1 Wl and s, we have a gap-preserving reduction from WMAx J'o to

MAX ~" with parameters (e, s), (d, s'), such that d and s ~ satisfy

Ct WlO~I "~ (C -- Wl)Ot 2

S "7 >1 WlOtl + W2a2 --

(1 -- S)fl"

Remark 8.12. We may assume that the gadgets have the same parameter ~3,

since we can transform an (al, 131)-fygadget and an (a2,132)-f2-gadget into an

(allY2,/31~2)-f1-gadget and an (a2~1,/31/32)-f2-gadget, respectively. The quality

of the gadgets is preserved by this transformation.

Proof of Lemma 8.11. Assume again that there are m constraints in our source

problem, wtm from ft and w2m from f2. Let ~t, ~2 be the number of replacement

constraints. By the same reasoning as above,

mwl(~l + m(c -

Wl)a2

c' >t

mWl gl

+ mw2~2

220 Chapter 8. Deriving Non-Approximability Results by Reductions

s' ~<

mwl(O~l -- f~) Jr mw2(o~2 --/~) Jr ms]3

mWl~l Jr mw2~2

Recall that our main interest in gadgets was to use them to encode the compu-

tation of the verifier from Theorem 8.3. The following theorem shows that we

should try to find (a, f~)-gadgets where the ratio ~ is as small as possible.

Theorem 8.13 (induced gap). For any constraint family Jr, if there exists

an (o~1,13)-gadget reducing PCo to jr and an (c~2,/3)-gadget reducing PC1 to jr,

then for any 7 > 0, MAX Jr is hard to approximate to within

OL1 Jr OL2 -- 7"

Proof. We can simply apply the previous lemma with the parameters c = 1 -

and s = 1 + ~ of the verifier from Theorem 8.3. For 7 = 7(~,~), this gives us

e ~ 1

s--; /> 1- ~ -7

2(Wl ~l-}-w2 a2)

and 7 -+ 0. We can ensure that at most half of the PC-constraints must be re-

duced with the larger ai since otherwise, we can simply complement all variables

in the reduction. The proof is completed by noting that under this condition,

the given term is minimal for wl = w2 -- 1/2. 9

Using Theorem 8.13 and the (4,1)-gadgets of BeUare et al. [BGS95] to reduce

PC to MAXE3SAT, Hs [H~s97b] was able to conclude that MAXE3SAT is

hard to approximate to within ~ - 6 (see Theorem 7.11).

Theorem 8.13 tells us that we should use gadgets with ratio ~ as small as

possible. It follows that an improved construction of a gadget may yield an

improved non-approximability result. Therefore, it is desirable to have lower

bounds on this "quality" of a certain gadget to understand if it is possible to

improve the known construction or if it is the best possible one. This question

was raised in [BGS95].

Despite its importance, the construction of gadgets remained an ad hoc task

and no uniform methods were known; for each verifier using a different kind of

test and each target problem new gadgets had to be found. Finally, Trevisan et

al. [TSSW96] developed an approach to resolve this situation. They showed how

the search for a gadget can be expressed as a linear program (LP). Solving the

LP with the help of a computer allows us to find provably optimum gadgets.

The main idea is to limit the search space of possible gadgets to a finite and

reasonably sized one. Note that this is not always possible (see Exercise 8.1). But

we can achieve this goal for some important constraint families by addressing

the following two questions.

8.4. Weighted vs. Unweighted Problems 221

1. Recall that a gadget is a collection of constraints and that constraints are

formed from some constraint family and a set of variables. Can we limit the

number of different possible constraints? The key will be a limitation of the

number of auxiliary variables.

2. A gadget may contain the same constraint more than once. How do we cope

with multiple occurrences of constraints? Note that in general there is no

a priori bound on the number of occurrences of a constraint in an optimal

gadget.

8.4 Weighted vs. Unweighted Problems

A simple way to deal with the second question is to assign a weight to each

possible constraint. Multiple occurrences of the same constraint can then be

represented by giving it a higher weight. So we are lead to define weighted

constraint satisfaction problems.

WEIGHTEDMAX .T"

Instance:

Given m constraints (C1, C2,...,

Cm}

from a constraint family 9 r on

n variables and associated positive rational weights wl, w2,..., win.

Problem: Find an assignment to the variables which maximizes the weighted

sum ~i~1 w~C~.

A gadget may again be thought of as an instance of a weighted constraint

satisfaction problem. Note however, that in this way we would only get non-

approximability results for weighted versions of optimization problems rather

than for unweighted ones. But fortunately, there is a result due to Crescenzi et

al. [CST96] which shows that for a large class of optimization problems, includ-

ing constraint satisfaction problems, the weighted versions are exactly as hard

to approximate as the unweighted ones.

In an instance of WEIGHTEDMAX .T" the weights can be arbitrary rationals. Let

POLYMAX .~ denote those instances of WEIGHTEDMAX ~" where the weights are

polynomially bounded integers and let SINGLEMAX ~" denote those instances of

MAX ~" where a constraint occurs at most once. The key step in showing that

unweighted constraint satisfaction problems are exactly as hard to approximate

as weighted versions of constraint satisfaction problems is to prove that the

polynomially bounded weighted version is a -

reducible (see Definition 1.32)

to the unweighted problem, i.e., POLYMAX~"

~iP SINGLEMAX~',

for any a >

1. This implies that the approximation threshold of POLYMAX 9 v is at most equal

to the approximation threshold of SINGLEMAX ~'. So the lower bounds obtained

for the weighted versions are also valid for the unweighted versions and we can

conclude that both versions have the same approximation threshold. The proof

of the

a - AP

reducibility relies on the notion of a

mixing set

of tuples which is

defined as follows.

222 Chapter 8. Deriving Non-Approximability Results by Reductions

Definition 8.14. Let n > O, k > 0 be integers. A set S C [n] k is called k-

ary (n,w,e,~)-mixing if for any k sets AI,... ,Ak C [n], each with at least ~n

elements, the following holds:

IISnA1 x ... x Akl-wlA~l"'lAkl I

IA~I"'IA~I

n~ <. ew n~

Note that by setting each Ai = In] we can immediately derive some bounds on

the size of S from the definition, namely (1 - E)w ~< I SI ~< (1 + e) w. The existence

of mixing sets can be shown by an easy probabilistic construction.

Lemma 8.15. For any integer k >1 2 and for any two rationals 6, 6 > O, two

constants no and c exist such that for any n >/no and for any w with cn <<. w <<.

n k, a k-ary (n,w,r set exists.

Proof. Construct a set S C_ [n] k by randomly selecting each element from [n] k

with probability w/n k. Then for any k sets A1,..., Ak C_ In] we have

IAll-..." IAkl

m := E(IS

...

Akl) = w nk

and therefore using Chernoff bounds (see Theorem 3.5) we get under the as-

sumption that all sets Ai satisfy IAil >t 6n for i = 1,..., k

e~ / m

Prob[lISnA, x... x Akl- ml /> era] <~ (1 _[._ ~.)1+~

e e on6 ~

Since ~ < 1 for all e > 0 and all 0 < ~ < 1 we have shown that there

exists a set S that is (n, w, e, ~)-mixing for c = 1 and no = 1. 9

In [Tre97] Trevisan proved that in fact mixing sets can be constructed in poly-

nomial time.

Theorem 8.16. For any integer k >1 2 and for any two rationals ~, ~ > O, two

constants no and c exist such that, for any n >>. no and for any w with cn <~ w <~

n k, a k-ary (n, w, 6, ~)-mixing set can be constructed in time polynomial in n.

Theorem 8.17. Let if: be a constraint family where each constraint function

has arity >1 2. Then, for any ~ > 1, it is the case that PoLYMAX~

~.~p

SINGLEMAX ~.

8.4. Weighted vs. Unweighted Problems 223

Proof.

Let r > 1 be an arbitrary but fixed rational (a supposed approximation

factor of an approximation algorithm for SINGLEMAX

~-). Our goal

is to develop

a reduction which, given any a > 1, allows us to construct an approximation

algorithm for PoLYMAX ~" with approximation factor 1 + a(r - 1).

Let

r = (C1,... ,Cm,w:,... ,Win)

be an instance of POLYMAX ~" over the vari-

able set X -- {x:,... ,xn}. Let h be the largest arity of a constraint in Y. The

idea to represent the weights in an unweighted instance is to duplicate the vari-

ables and constraints in a suitable way by making use of the properties of mixing

sets. We can choose r ~ e (0, 1/2) such that

1 (1 + + 2 (1

~>r-1 1-:

Let no and c be constants such that Theorem 8.16 holds for every k = 2,..., h

and let

Wm,~= =

maxi{wi}. Now we rescale the weights by multiplying each

with a factor of c2n0Wma=2 and choose N = cnow,~=. Then N > no and

cN <~

wi <~ N 2

holds for all i e [m] . Theorem 8.16 ensures that, for every

cN <~ w <~

N 2 and every k = 2,..., h, a k-ary (N, w, :, ~)-mixing set S~ can be efficiently

constructed. We are now^ready to define an instance ~ of SINGLEMAX .T" as

follows. The variable set X of 9 has N copies of every variable of X:

= {~: i 9 [N,J 9 IN]}.

For a k-ary constraint

Cj = f(xil,...,xi~)

of weight

we define a set of

constraints, Cj, as follows:

= {s(=t:,...,=,~ : 9 s[,}.

Finally ~ is defined as the union of the Cj sets

je[m]

First of all we can show that the values of optimal solutions are similar. We

claim that for any assignment T for ~ there exists an assignment ~ for ~ such

that v(~, .~) ~ (1 - e)v(r T). To see this, simply define ~ as follows: for any

3 9 X set ~(x~) = ~(xi). We then have

variable xi

v(~,~) = Z[{C 9 Cj: ~ satisfies C}[ = Z [CJ[

i:~ satisfies

= Z IS[ '1 >~

(1 - ~)v(,~, r).

j:r satisfies c~

As a corollary we get Opt(~) >/ (1 - r Opt(~). On the other hand, we need

a way to derive an assignment T for 9 given any assignment ~ for 4. We claim

that this can be done in polynomial time in such a way that

224 Chapter 8. Deriving Non-Approximability Results by Reductions

v('~,r) >1

1 ^

~).

(1 + ~')(1 + 2h(1 -- (1 -- 6)h)) v(@'

In a first step, we will transform @ into an assignment "~' such that for every

variable

xi E X

at least

and at most (1 -

6)N

copies of

are set to

TRUE.

If this condition is not fulfilled for, say

xi E X,

we can switch the value of

some of its copies. Note that it is always possible to achieve the condition by

switching at most 6N copies. Unfortunately, this might reduce the number of

satisfied constraints. The difference between the measure of @ and that of ~'

is bounded by the number of constraints where a switched variable occurs. We

claim that in Cj this number is at most (1 + ~)wj - (1 - :)(1 -

6)kwj

where k is

the arity of Cj. By construction [Cj[ ~ (1 +

Since at most

copies of a

variable are switched, we know that at least (1 - 6)N copies remain unchanged.

Since Cj was constructed by a mixing set Sk # , we can conclude that in at least

(1 - :)(1 -

6)kwj <~

(1 -- e)(1 --

6)hwj

constraints of Cj no variable was switched,

and this proves the claim. Summing over all j 9 [m] we get

v(~,'~) - v(~,~") <

Wtot"

(1 + e - (1 - :)(1 - 6) h)

where

Wtot -- ~_,j wj.

Now we will show how to derive an assignment for r from

@'. For any variable

xi 9 X,

let

I{J: =

TRUE}I

Pi= N

be the fraction of copies of

whose value is set to

TRUE by "r'.

We can derive

a random assignment Tn for the variables in X by setting variable

to TRUE

with probability Pi, i.e., Prob[rR(xi)

= TRUE]

= Pi.

We are now interested

in the probability that such a random assignment satisfies a k-ary constraint

Cj = f(xi,,... ,xik)

of @ of weight

wj.

Let

SATj C

{TRUE,

FALSE} k be

the set

of satisfying assignments to the variables of Cj. We then have

Prob[rR satisfies

Cj]

-'- E Prob[vR(xi,)

= bl,. . . , "rR(xi~) = bk]

(bx

..... bk)ESAT,

= E I'Ii~l IlJ 9 [g]: @'(~) =

bi}l

N k

(bl ..... b~)ESAT,

Note that each set of indices

Ai = {j e

[N] : ~'(x{) = bi} has size at least 6N.

Thus, we can use the mixing property of the set S~" and continue

Is:' hA, • •

(bx

..... bk)ESATj

(1 + :)wj

[{C E Cj: ~' satisfies C}[

I> (I + e:)wj