wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Almost-Clique Problem
        
(Message started by: Barukh on Jun 14^th, 2013, 1:16am)

Title: Almost-Clique Problem
Post by Barukh on Jun 14^th, 2013, 1:16am

It is well known that Clique Decision problem (http://www.cs.washington.edu/education/courses/csep521/99sp/lectures/lecture04/sld018.htm) 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.

Title: Re: Almost-Clique Problem
Post by TenaliRaman on Jun 16^th, 2013, 4:39pm

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.