6. The Half Clique decision problem is the problem of deciding if a simple graph G...

 

Transcribed Image Text:

6. The Half Clique decision problem is the problem of deciding if a simple graph G = (V,E) has a Clique of size |V|/2. (a) Provide a general and precise description of a contraction reduction f from Clique to Half Clique. Defend your answer, meaning prove that (G, k) is a positive instance of Clique iff f(G,k) is a positive instance of Half Clique. Hint: Clique is the decision-version problem of Max Clique. (20 pts) (b) Draw f(G, k = 3) where G is the graph shown below. (5 pts) 5 6. The Half Clique decision problem is the problem of deciding if a simple graph G = (V,E) has a Clique of size |V|/2. (a) Provide a general and precise description of a contraction reduction f from Clique to Half Clique. Defend your answer, meaning prove that (G, k) is a positive instance of Clique iff f(G,k) is a positive instance of Half Clique. Hint: Clique is the decision-version problem of Max Clique. (20 pts) (b) Draw f(G, k = 3) where G is the graph shown below. (5 pts) 5