<p>Consider a graph on vertex set <span class="math-container">$V_1\cup V_2\cup V_3\cup V_4\cup \{a,b,c,d\}$</span> where <span class="math-container">$|V_1|=|V_2|=|V_3|=|V_4|=n$</span>. The edge set <span class="math-container">$E$</span> is covered by <span class="math-container">$C=\{V_1\cup\{a,c\},V_2\cup\{a,d\},V_3\cup\{b,c\},V_4\cup\{b,d\},\{a,b\},\{c,d\}\}$</span>.</p>
<p>When <span class="math-container">$n$</span> is large enough, any minimalist cover must contain the four maximum cliques <span class="math-container">$V_1\cup\{a,c\}$</span> and so on, so it is not hard to show that <span class="math-container">$C$</span> is minimalist. However replacing the two edges <span class="math-container">$\{a,b\}$</span> and <span class="math-container">$\{c,d\}$</span> with a single clique <span class="math-container">$\{a,b,c,d\}$</span> results in less number of cliques.</p>

CC BY-SA 4.0
2020-12-29T10:54:22.197Z
Nice, thank you! The two coverings have the same sum of clique sizes; do you think we may go further and find a minimalist covering with a sum of clique size _strictly lower_ than the one of minimal coverings?
Matthieu Latapy
CC BY-SA 4.0
2020-12-29T11:05:05.297Z
A friend just pointed me the following paper: [Assignment-minimum clique coverings](https://doi.org/10.1145/2133803.2275596) (Ennis, Fayle, Ennis, 2012) that seems to solve the question.
Matthieu Latapy
CC BY-SA 4.0
2020-12-29T03:49:36.840Z
2020-12-29T03:49:36.840Z
Wei Zhan
<p>Given a graph <span class="math-container">$G=(V,E)$</span>, a <strong>clique edge cover</strong> is a collection <span class="math-container">$C$</span> of subsets of <span class="math-container">$V$</span> such that each element <span class="math-container">$c$</span> of <span class="math-container">$C$</span> is a clique (<span class="math-container">$c \times c \subseteq E$</span>) and <span class="math-container">$G$</span> is the union of these cliques (<span class="math-container">$E = \bigcup_{c\in C} c\times c$</span>).</p>
<p>The cover is said to be minimal if <span class="math-container">$|C|$</span> is <strong>minimal</strong>, <em>i.e.</em> the number of cliques used to cover the graph is minimal.</p>
<p>Let us say that the cover is <strong>minimalist</strong> if <span class="math-container">$\sum_{c\in C} |c|$</span>, <em>i.e.</em> the sum of clique sizes, is minimal.</p>
<p>(Is there a better term than minimalist here? Does it appear in the literature?)</p>
<p><strong>There exists minimal covers that are not minimalist covers.</strong></p>
<p>Consider for instance, the graph where <span class="math-container">$V=\{a,b,c,d,e\}$</span> and <span class="math-container">$E$</span> is covered by <span class="math-container">$C = \{\{a,b,c\}, \{b,c,d\}, \{c,d,e\}\}$</span>. This is a minimal covering of the graph, but not a minimalist one, since it is also covered by <span class="math-container">$\{\{a,b,c\}, \{b,d\}, \{c,d,e\}\}$</span>.</p>
<p><em><strong>Question:</strong></em>
<strong>Is the converse true?</strong> Is there any graph having a minimalist cover that contains more than the minimal number of cliques needed to cover it?</p>

CC BY-SA 4.0
2020-12-29T11:17:41.683Z
It turns out that minimalist covers are known as assignment-minimum coverings (which I will add to the question title), and that there are graphs for which no minimum clique covering is assignment-minimum, see ["Assignment-minimum clique coverings"](https://doi.org/10.1145/2133803.2275596) (Ennis, Fayle, Ennis, 2012).
Matthieu Latapy
<graph-theory><graph-algorithms><clique><bipartite-graphs><covering-problems>
Minimal clique edge cover vs minimalist (assignment-minimum) ones
Matthieu Latapy
# Minimal clique edge cover vs minimalist (assignment-minimum) ones

(Asked by: username_0 on 2020-12-28)

Given a graph $G=(V,E)$, a **clique edge cover** is a collection $C$ of subsets of $V$ such that each element $c$ of $C$ is a clique ($c \times c \subseteq E$) and $G$ is the union of these cliques ($E = \bigcup\_{c\in C} c\times c$).

The cover is said to be minimal if $|C|$ is **minimal**, *i.e.* the number of cliques used to cover the graph is minimal.

Let us say that the cover is **minimalist** if $\sum\_{c\in C} |c|$, *i.e.* the sum of clique sizes, is minimal.

(Is there a better term than minimalist here? Does it appear in the literature?)

**There exists minimal covers that are not minimalist covers.**

Consider for instance, the graph where $V=\{a,b,c,d,e\}$ and $E$ is covered by $C = \{\{a,b,c\}, \{b,c,d\}, \{c,d,e\}\}$. This is a minimal covering of the graph, but not a minimalist one, since it is also covered by $\{\{a,b,c\}, \{b,d\}, \{c,d,e\}\}$.

***Question:***
**Is the converse true?** Is there any graph having a minimalist cover that contains more than the minimal number of cliques needed to cover it?

**Tags:** graph-theory, graph-algorithms, clique, bipartite-graphs, covering-problems

> **Comments:**
> **username_0**: It turns out that minimalist covers are known as assignment-minimum coverings (which I will add to the question title), and that there are graphs for which no minimum clique covering is assignment-minimum, see ["Assignment-minimum clique coverings"](https://doi.org/10.1145/2133803.2275596) (Ennis, Fayle, Ennis, 2012).  

---

## 1 answers

### Answer by username_1 on 2020-12-29. Score: 4 | Accepted answer

Consider a graph on vertex set $V\_1\cup V\_2\cup V\_3\cup V\_4\cup \{a,b,c,d\}$ where $|V\_1|=|V\_2|=|V\_3|=|V\_4|=n$. The edge set $E$ is covered by $C=\{V\_1\cup\{a,c\},V\_2\cup\{a,d\},V\_3\cup\{b,c\},V\_4\cup\{b,d\},\{a,b\},\{c,d\}\}$.

When $n$ is large enough, any minimalist cover must contain the four maximum cliques $V\_1\cup\{a,c\}$ and so on, so it is not hard to show that $C$ is minimalist. However replacing the two edges $\{a,b\}$ and $\{c,d\}$ with a single clique $\{a,b,c,d\}$ results in less number of cliques.

> **Comments:**
> **username_0**: Nice, thank you! The two coverings have the same sum of clique sizes; do you think we may go further and find a minimalist covering with a sum of clique size _strictly lower_ than the one of minimal coverings?  
> **username_0**: A friend just pointed me the following paper: [Assignment-minimum clique coverings](https://doi.org/10.1145/2133803.2275596) (Ennis, Fayle, Ennis, 2012) that seems to solve the question.  

---

