Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!swrinde!cs.utexas.edu!uunet!garfield!odie.cs.mun.ca!harold
From: harold@stretch.cs.mun.ca (Harold Wareham(Todd))
Newsgroups: comp.theory
Subject: Request for Help: Properties of [PS] 3-SAT -> CLIQUE Reduction
Message-ID: <1991Apr11.193630.17416@garfield.cs.mun.ca>
Date: 11 Apr 91 19:36:30 GMT
Sender: nntp@garfield.cs.mun.ca (NNTP server account)
Organization: CS Dept, Memorial University of Newfoundland
Lines: 57
Originator: harold@odie.cs.mun.ca

I have a question concerning a statement made in:

 Papadimitriou, C.H., and Yannakakis, M. (1982)  "The Complexity of
	Facets (and Some Facets of Complexity)", JOURNAL OF
	COMPUTER AND SYSTEM SCIENCES, 28, 244-259.

Specifically, in their proof for Theorem 1 (pp. 248-249), they state:

	"THEOREM 1: Exact Clique is Dp-complete

	 Proof: Reduce SAT-UNSAT to it. Starting from (F,F'), we can 
	        now construct two graphs G and G' and two integers k, k'
	        such that the maximum clique of G is of size k if F is 
	        satisfiable, and of size k - 1 otherwise, and
		similarly for G'. It is easy to see that this holds for
		standard transformations from SAT to clique [PS] ..."

Now, [PS] refers to

Papadimitriou, C.H, and Steiglitz, K. (1982)  COMBINATORIAL
	OPTIMIZATION: ALGORITHMS AND COMPLEXITY. Prentice-Hall, Inc;
	Englewood Cliffs, NJ.

and specifically to the reduction in Theorem 15.3 in chapter 15 on page
360 of this book, in which Clique is proved NP-complete by showing that
3-SAT polynomially many-one reduces to it (the proof is not overly
complicated, but it is a bit long to go into detail here).

ANYWAY ... my question is this: Though I can see how the reduction
given in theorem 15.3 has clique size = k if F is satisfiable, I
cannot for the life of me see how clique size = (k - 1) is F is not
satisfiable. If anyone can see this, would they please point out to
me why this is so?

(This is actually part of my attempts at unravelling some of the 
 proofs given in the latter half of

Wagner, K. W. (1987)  "More complicated questions about maxima and
	minima, and some closures of NP", THEORETICAL COMPUTER SCIENCE,
	51, 53-80.

 In particular, Theorem 6.1, pp. 67-68. Perhaps this will help make
 my situation a bit clearer).

Any help would be much appreciated. I hope this request isin't too
stupid.

- Todd

P.S.- For the record, this is not part of an assignment for some
	course, but is rather research for my M.Sc. thesis.

Todd Wareham	harold@odie.cs.mun.ca	|"Success in science depends not
Department of Computer Science		| only on rational argument but
Memorial University of Newfoundland	| on a mixture of subterfuge,
St. John, NF, Canada			| rhetoric, and propaganda"
					|    - Feyerabed