Tell me more ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.
up vote 2 down vote favorite

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.

share|improve this question

1 Answer

up vote 6 down vote accepted

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.

share|improve this answer
so if I have a clique of size four, of four vertices, how would the graph look like? – user1675999 Dec 4 '12 at 14:41
The wikipedia page for complete graphs has a bunch of examples (including $K_4$): en.wikipedia.org/wiki/Complete_graph – William Macrae Dec 4 '12 at 14:45
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? – user1675999 Dec 4 '12 at 16:47
1  
@user1675999: see this image: cs.mcgill.ca/~ethan/img/cliquecover.png – Vor Dec 4 '12 at 17:56

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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