1
$\begingroup$

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?

Improve this question
$\endgroup$
  • $\begingroup$ Have you tried fixing the value of $C$? $\endgroup$ – Yuval Filmus May 21 '19 at 15:23
  • $\begingroup$ 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. $\endgroup$ – Klasj May 21 '19 at 15:29
  • $\begingroup$ That's different from your post. Which question do you want answered? $\endgroup$ – Yuval Filmus May 21 '19 at 15:30
  • $\begingroup$ Hint: all vertices in a $k$-clique have degree at least $k-1$. $\endgroup$ – Yuval Filmus May 21 '19 at 15:30
  • $\begingroup$ I edited the question with C being fixed. $\endgroup$ – Klasj May 21 '19 at 15:34
3
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.