# Reducing CLIQUE to Super Connector problem

I am trying to show that our problem is NP-Complete by reducing the known problem CLIQUE to our problem.

Regular CLIQUE problem:

Input: An undirected graph $$G$$ and a positive integer $$K$$.

Goal: Does $$G$$ have a clique of size at least $$K$$?

Our problem:

Input: An undirected graph $$G$$ and a positive integer $$K$$.

Goal: Is there a group of size $$K$$ of super connectors in $$G$$?

A super connector is a node with at least $$C$$ (i.e., a fixed number of) edges. A group $$S$$ of super connectors is a set of super connectors all connected to each other.

A group of super connectors is thereby a clique and a return value of TRUE from our problem will result in TRUE in the CLIQUE problem as well.

My idea to solve this is that I modify the graph by removing all nodes that aren't super connectors. We are then left with a graph where every node is super connectors and can then input the graph in the CLIQUE problem to see if there exists a clique and thereby get a solution for our problem. By modifying the graph like this both of the problems will give the same outputs with the same inputs. Am I on the right path or completely wrong?

• Have you tried fixing the value of $C$? – Yuval Filmus May 21 '19 at 15:23
• The task I am working on actually states that C is fixed, but I am not sure how that is different from getting C as an input. – Klasj May 21 '19 at 15:29
• That's different from your post. Which question do you want answered? – Yuval Filmus May 21 '19 at 15:30
• Hint: all vertices in a $k$-clique have degree at least $k-1$. – Yuval Filmus May 21 '19 at 15:30
• I edited the question with C being fixed. – Klasj May 21 '19 at 15:34

The simplest NP-hardness reduction is as follows. Suppose we are given an instance $$(G,k)$$ of CLIQUE. If $$k \leq c$$ then we solve CLIQUE by brute force in time $$O(n^c)$$. Otherwise, $$G$$ has a $$k$$-clique iff it has a $$k$$-clique consisting of super-connectors. This is because any vertex in a $$k$$-clique must have degree at least $$k-1 \geq c$$, and so is a super-concentrator.