0
$\begingroup$

WEIGHTED-CLIQUE

  • input: a undirected graph G that has weighted edges and 2 natural numbers a, b

  • question: does G have a clique of size a with total weight of b?

I want to prove that this is NP-hard (assuming weighted-clique $\in NP$)

So I would have to prove

$VertexCover \leq_P WeightedClique$

Need to show the transformation: $(G, k) \to (G', k', d)$

Which ill do by using the fact that $C$ is a vertex cover in $G = (V, E)$ whenever $\bar{C}$ is a clique in $G = (V, E)$ so $\overline{C} = |V| - C$

Hence we can let $G' = \overline{G}$ and $k' = |V| - k$.

I will draw example graphs to illustrate this:

enter image description here

I put 1's in $G'$ just to show that they're weighted as of right now, they have no purpose since I'm not sure how to integrate them into this problem yet.

So ultimately to prove this I need to show

  • If there is a solution to $VERTEXCOVER(G, k)$, then there must be a solution to WEIGHTEDCLIQUE$(\overline{G}, |V | − k, d)$ (1)

  • if there is a solution to WEIGHTEDCLIQUE$(\overline{G}, |V | − k, d)$, then there must be a solution to VERTEXCOVER$(G, k)$ (2)

I only know how to do the (2) part since the $d$ number could just be ignored.

(2) Using the fact from above where $C$ is a vertex cover we know that

If $\forall u, v \in V$, if $u, v \in C$, then $(u, v) \in E$

Taking the contrapositive

$\Leftrightarrow \forall u,v \in V$, if $(u, v) \in \overline{E}$, then $(u \in \overline{C} \text{ or } v \in \overline{C})$. Which makes it clear that $\overline{C}$ is a clique. This is also done in polynomial time since we are going over all pairs of vertices in the original graph which is done in polynomial time.

Now for (1) I'm not sure how to use the vertex cover and get some d such that it holds, if even possible.

Any help appreciated

edit: did wrong side by accident, fixed it

$\endgroup$
  • 1
    $\begingroup$ If you want to prove weighted-clique is NP-hard, then you need to reduce vertex cover to it, not the other way around. $\endgroup$ – dkaeae Jul 11 at 8:46
  • $\begingroup$ Oh that would make a lot more sense... $\endgroup$ – bob Jul 11 at 9:26
  • $\begingroup$ The fact that 𝐶 is a vertex cover does not imply "∀𝑢,𝑣∈𝑉, if 𝑢,𝑣∈𝐶, then (𝑢,𝑣)∈𝐸". $\endgroup$ – Steven Jul 11 at 15:21
0
$\begingroup$

Let $G=(V,E)$ be an unweighted graph (think of all the edges as having weight $1$), $n=|V|$, and $\bar{G}$ be the edge-complement of $G$.

Now, $C$ is a vertex cover of $G$ iff $\bar{C} = V \setminus C$ is an independent set of $G$, that is, iff $\bar{C}$ is a clique of $\bar{G}$.

When you combine this with the fact that a clique of size $k$ has $\binom{k}{2} = \frac{k^2-k}{2}$ edges you get: "There is a vertex cover of size $k$ in $G$ iff $\bar{G}$ contains a clique of size $a = n-k$ and weight $b = \binom{n-k}{2}$."

In fact, as far as this reduction is concerned, you can drop either the size or the weight constraint from your clique problem since one implies the other.

$\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.