harold@stretch.cs.mun.ca (Harold Wareham(Todd)) (04/12/91)
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