wu :: forums
wu :: forums - Almost-Clique Problem

Welcome, Guest. Please Login or Register.
Sep 20th, 2019, 9:06am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   cs
(Moderators: Eigenray, Icarus, SMQ, ThudnBlunder, william wu, Grimbal, towr)
   Almost-Clique Problem
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Almost-Clique Problem  (Read 7366 times)
Barukh
Uberpuzzler
*****






   


Gender: male
Posts: 2276
Almost-Clique Problem  
« on: Jun 14th, 2013, 1:16am »
Quote Quote Modify 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: male
Posts: 1001
Re: Almost-Clique Problem  
« Reply #1 on: Jun 16th, 2013, 4:39pm »
Quote Quote Modify 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
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright 2000-2004 Yet another Bulletin Board