Author |
Topic: Almost-Clique Problem (Read 7858 times) |
|
Barukh
Uberpuzzler
Gender: 
Posts: 2276
|
 |
Almost-Clique Problem
« on: Jun 14th, 2013, 1:16am » |
 Quote  Modify
|
It is well known that Clique Decision problem is NP-complete.
Define the Almost-Clique decision problem as follows:
Determine whether graph G has a set U of k vertices, such that for every pair of vertices in U but one there is an edge in E connecting them.
Prove or disprove:
Almost Clique decision problem is NP-complete.
|
|
 IP Logged |
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Almost-Clique Problem
« Reply #1 on: Jun 16th, 2013, 4:39pm » |
Quote Modify
|
An almost-clique of size k has a k-1 size clique sub-graph. So, we can take F (from the link) with k-1 clauses. We add a dummy literal which is grounded to true and create an additional clause with just this dummy literal and append it to the end of F, call it F'. We construct graph out of F' just like the one prescribed in the link, except that the dummy literal is not connected to all the remaining k-1 clauses, we arbitrarily choose k-2 clauses to connect to.
Now, any solution to F is also a solution to F'. Therefore, a solution to F gives a k size almost-clique. Similarly, given a k sized almost-clique in G, just remove the dummy literal and assign the remainder values and one should obtain the solution to F.
|
| « Last Edit: Jun 16th, 2013, 4:40pm by TenaliRaman » |
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print