<p>Here is a paper that deals with this problem:</p>

<p>John M. Ennis, Charles M. Fayle, and Daniel M. Ennis: <a href="http://dx.doi.org/10.1145/2133803.2275596" rel="nofollow">Assignment-minimum clique coverings</a>. Journal of Experimental Algorithmics 17(1), 2012.</p>

<p>It also gives some heuristics and experimental results. They don't give worst-case approximation ratios; minimizing the number of cliques instead of the sum of their sizes has only fairly weak approximation guarantees, so I guess it would be similar here.</p>

CC BY-SA 4.0
2020-06-09T01:56:16.390Z
Maybe I misunderstood something, but would simply taking the $m$ edges minimizes the sum cardinality. It cannot be smaller than $m$, right?
Yixin Cao
CC BY-SA 3.0
2013-02-07T12:10:19.260Z
2013-02-07T12:10:19.260Z
Falk Hüffner
<p>I'd like to take an undirected graph and express it (meaning all of its edges) using only cliques (ideally minimizing their sum cardinality).</p>

<p>It's clear that actually finding the minimum solution is at least as hard as the set-cover problem, but set-cover has good approximation algorithms.
Does anyone know a good approximation algorithm for this?</p>

<p>Particularly, if I start with each edge as its own clique and then arbitrarily choose two cliques from my list (whose union also forms a clique) and merge them and do this over and over until I can't merge any more, what's the worst case (as a ratio / the minimal solution)? Is there some heuristic I should use to determine what to merge next?</p>

CC BY-SA 3.0
2013-02-07T00:59:59.093Z
As an example, in the graph where A B C D form a square and there's a diagonal edge between A and C, the solution with minimal sum cardinality is {ABC, CDA} for a total of 6.  Other solutions would be {ABC, CD, AD} with sum cardinality 7 and {AB, BC, CD, AC, AD} with sum cardinality 10
dspyz
<graph-algorithms><approximation-algorithms><set-cover><clique>
How to approximate minimum clique edge cover
dspyz
# How to approximate minimum clique edge cover

(Asked by: username_0 on 2013-02-07)

I'd like to take an undirected graph and express it (meaning all of its edges) using only cliques (ideally minimizing their sum cardinality).

It's clear that actually finding the minimum solution is at least as hard as the set-cover problem, but set-cover has good approximation algorithms.
Does anyone know a good approximation algorithm for this?

Particularly, if I start with each edge as its own clique and then arbitrarily choose two cliques from my list (whose union also forms a clique) and merge them and do this over and over until I can't merge any more, what's the worst case (as a ratio / the minimal solution)? Is there some heuristic I should use to determine what to merge next?

**Tags:** graph-algorithms, approximation-algorithms, set-cover, clique

> **Comments:**
> **username_0**: As an example, in the graph where A B C D form a square and there's a diagonal edge between A and C, the solution with minimal sum cardinality is {ABC, CDA} for a total of 6.  Other solutions would be {ABC, CD, AD} with sum cardinality 7 and {AB, BC, CD, AC, AD} with sum cardinality 10  

---

## 1 answers

### Answer by username_1 on 2013-02-07. Score: 2 | Accepted answer

Here is a paper that deals with this problem:

John M. Ennis, Charles M. Fayle, and Daniel M. Ennis: [Assignment-minimum clique coverings](http://dx.doi.org/10.1145/2133803.2275596). Journal of Experimental Algorithmics 17(1), 2012.

It also gives some heuristics and experimental results. They don't give worst-case approximation ratios; minimizing the number of cliques instead of the sum of their sizes has only fairly weak approximation guarantees, so I guess it would be similar here.

> **Comments:**
> **username_2**: Maybe I misunderstood something, but would simply taking the $m$ edges minimizes the sum cardinality. It cannot be smaller than $m$, right?  

---

