Informally, we want to partition the edges of a graph into a few cliques. Given $G=(V, E)$, we want to find subsets $V_1,\dots, V_k\subset V$ such that $E = E[V_1]\dot\cup \dots \dot\cup E[V_k]$, where induced subgraphs are complete $E[V_i]=\binom{|V_i|}{2}$, and we want to maximize $\sum_i \binom{|V_i|}{2}$.

Is there an efficient algorithm to exactly/approximately solve relaxed clique cover? In particular, I'm curious if the following algorithm has some probabilistic guarantee:

Greedy algorithm:

  1. Pick an random order of vertices $v_1,\dots, v_n$.
  2. At step $i$, check if vertex $v_i$ is connected to all vertices in one of the subsets $V_1,\dots, V_k$ and add it to that set if it exists.
  3. If no such subset exists, create a new subset containing this vertex only $V_{k+1}=v_i$.
  • $\begingroup$ Instead of trying to guess the problem, I suggest asking the professor for a clarification. $\endgroup$ – Yuval Filmus Jun 14 at 10:11
  • $\begingroup$ I think it should be fixed now, thanks. there is no professor to ask for clarification :) $\endgroup$ – Ameer Jewdaki Jun 14 at 10:16

Your Answer

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

Browse other questions tagged or ask your own question.