Author 
Topic: AlmostClique Problem (Read 7351 times) 

Barukh
Uberpuzzler
Gender:
Posts: 2276


AlmostClique Problem
« on: Jun 14^{th}, 2013, 1:16am » 
Quote Modify

It is well known that Clique Decision problem is NPcomplete. Define the AlmostClique 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 NPcomplete.


IP Logged 



TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001


Re: AlmostClique Problem
« Reply #1 on: Jun 16^{th}, 2013, 4:39pm » 
Quote Modify

An almostclique of size k has a k1 size clique subgraph. So, we can take F (from the link) with k1 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 k1 clauses, we arbitrarily choose k2 clauses to connect to. Now, any solution to F is also a solution to F'. Therefore, a solution to F gives a k size almostclique. Similarly, given a k sized almostclique in G, just remove the dummy literal and assign the remainder values and one should obtain the solution to F.

« Last Edit: Jun 16^{th}, 2013, 4:40pm by TenaliRaman » 
IP Logged 
Self discovery comes when a man measures himself against an obstacle  Antoine de Saint Exupery



