2
$\begingroup$

I am really confused about clique problem and clique cover problem. I tried googling it,but I don't see to be able to visualise the clique cover problem.

$\endgroup$
6
$\begingroup$

A clique is a simple undirected graph with all of the possible edges. It is also known as a complete graph, but clique is more often used to referring to subgraphs that are complete graphs.

The clique cover problem asks whether a graph's vertices can be partitioned into $k$ or fewer sets such that each set of vertices induces a clique. That is, $V = V_1 \cup V_2 \cdots \cup V_k$ such that if $u, v \in V_i$ then $uv \in E$. For example, $C_4$ (a cycle of 4 vertices) can be partitioned into 2 cliques by choosing two non-adjacent edges. If the vertices were 1, 2, 3, 4 and the edges 12, 23, 34, 14, then we could write $V = \{1,2\} \cup \{3,4\}$, and check that $12$ and $34$ were edges as required.

This is different from the clique problem, which asks whether there is a clique in the graph of size at least $k$ (and does not care about the structure of the rest of the graph. For example, in $C_4$, there is a clique of size 2.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ so if I have a clique of size four, of four vertices, how would the graph look like? $\endgroup$ – user1675999 Dec 4 '12 at 14:41
  • $\begingroup$ The wikipedia page for complete graphs has a bunch of examples (including $K_4$): en.wikipedia.org/wiki/Complete_graph $\endgroup$ – William Macrae Dec 4 '12 at 14:45
  • $\begingroup$ what I am confused is according to the question that I was provided, it says clique cover problem exists a partition of V into k disjoint subsets. If that is the case then I can take the clique K4, and break it into V={1,2}U{3,4} and have two subsets, and from another question that I asked, for the four single vertices , will require two colors to color? $\endgroup$ – user1675999 Dec 4 '12 at 16:47
  • 1
    $\begingroup$ @user1675999: see this image: cs.mcgill.ca/~ethan/img/cliquecover.png $\endgroup$ – Vor Dec 4 '12 at 17:56

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.