[Solved]: The equivalence relations cover problem (in graph theory)

Problem Detail: 

An equivalence relation on a finite vertex set can be represented by an undirected graph that is a disjoint union of cliques. The vertex set represents the elements and an edge represents that two elements are equivalent.

If I have a graph $G$ and graphs $G_1,\dots,G_k$, we say that $G$ is covered by $G_1,\dots,G_k$ if the set of edges of $G$ is equal to the union of the sets of edges of $G_1,\dots,G_k$. The edge sets of $G_1,\dots,G_k$ do not need to be disjoint. Note that any undirected graph $G$ can be covered by a finite number of equivalence relations (i.e., disjoint union of cliques graphs).

I have several questions:

• What can be said about the minimal number of equivalence relations required to cover a graph $G$?
• How can we compute this minimal number?
• How can we compute an explicit minimum cover of $G$, i.e., a set of equivalence relations whose size is minimal and which cover $G$?
• Does this problem has any applications apart from partition logic (the dual of the logic of subsets)?
• Does this problem has a well established name?

---

Given the various misunderstandings indicated by the comments, here are some pictures to illustrate these concepts. If you have an idea for an easier to understand terminology (instead of "cover", "equivalence relation", "disjoint union of cliques" and "not necessarily disjoint" union of edge sets), feel free to let me know.

Here is a picture of a graph and one equivalence relation covering it:

Here is a picture of a graph and two equivalence relations covering it:
It should be pretty obvious that at least two equivalence relations are required.

Here is a picture of a graph and three equivalence relations covering it:
It's less obvious that at least three equivalence relations are required. Lemma 1.9 from Dual of the Logic of Subsets can be used to show that this is true. The generalization of this lemma to nand operations with more than two inputs was the motivation for this question.

Asked By : Thomas Klimpel

Answered By : Juho

The problem is known as the equivalence covering problem in graph theory. It is upper bounded by the clique covering number (the minimum collection of cliques such that each edge of the graph is in at least one clique). There are many similar problems and definitions; one has to be very careful here. These two numbers are denoted by $\text{eq}(G)$ and $\text{cc}(G)$, respectively.

There are special graph classes where the exact value or a good upper bound for either number is known. In general, to the best of my knowledge, the best bounds are given by Alon [1]:

$$\log_2 n - \log_2 d \leq \text{eq}(G) \leq \text{cc}(G) \leq 2e^2 (\Delta+1)^2 \ln n,$$

where $\Delta$ is the maximum degree of $G$. By the way, a covering with $\lceil n^2/4 \rceil$ triangles and edges is always possible (cf. Mantel's theorem), and this is easy to find algorithmically as well.

Not surprisingly, computing either number is $\sf NP$-complete. Even for split graphs, computing $\text{eq}(G)$ is $\sf NP$-hard (but can be approximated within an additive constant 1) as shown in [2]. It is also hard to compute for graphs in which no two triangles have a vertex in common [3].

---

[1] Alon, Noga. "Covering graphs by the minimum number of equivalence relations." Combinatorica 6.3 (1986): 201-206.

[2] Blokhuis, Aart, and Ton Kloks. "On the equivalence covering number of splitgraphs." Information processing letters 54.5 (1995): 301-304.

[3] Kučera, Luděk, Jaroslav Nešetřil, and Aleš Pultr. "Complexity of dimension three and some related edge-covering characteristics of graphs." Theoretical Computer Science 11.1 (1980): 93-106.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/27828