# Edge-disjoint clique cover

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$$.
• Instead of trying to guess the problem, I suggest asking the professor for a clarification. – Yuval Filmus Jun 14 at 10:11
• I think it should be fixed now, thanks. there is no professor to ask for clarification :) – Ameer Jewdaki Jun 14 at 10:16