10
$\begingroup$

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: graph and one equivalence relation covering it

Here is a picture of a graph and two equivalence relations covering it: 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: 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.

$\endgroup$
  • 1
    $\begingroup$ It is a well-known NP-Complete problem. en.wikipedia.org/wiki/Clique_cover_problem $\endgroup$ – gardenhead Jun 19 '14 at 1:04
  • $\begingroup$ @StephenBly Maybe it is a well known problem, but the wikipedia link you gave doesn't really help me. The article talks about a vertex cover problem, but the question here is concerned with an edge cover problem. Also note that an equivalence relation is not a clique, but a disjoint union of cliques. $\endgroup$ – Thomas Klimpel Jun 19 '14 at 1:16
  • $\begingroup$ What do you mean an equivalence relation is a disjoin union of cliques? The vertex set represents the elements and an edge represents that two elements are equivalent. If that's not the representation you're using then you should make it clear. $\endgroup$ – gardenhead Jun 19 '14 at 1:35
  • 3
    $\begingroup$ @StephenBly I don't think it's the same problem, the clique cover problem ask for the minimum number of cliques that covers the vertices of graph, here we seek the minimum number of equivalence relations to cover the edges of the graph. It's easy to see the upper bound is $n-1$ in this case, as we can partition any graph of $n$ vertices into at most $n-1$ matchings. $\endgroup$ – Chao Xu Jun 19 '14 at 2:03
  • 3
    $\begingroup$ @YuvalFilmus The question asks about the least number of equivalence relations whose union is exactly the edge relation of the given graph, not whose union merely includes the given graph. $\endgroup$ – David Richerby Jun 19 '14 at 10:21
4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Corollary 1.3 from [1] is exactly what I needed (in the version that applies to the complements of a path). Now I no longer have an excuse for not writting the paper about the general implication "(A,B,C,...) imply (Z,Y,X, ...)" (the sequent from sequent calculus) in partition logic and similar non-classic logics. But I guess I will not be writting it for at least another half year. And maybe I even find a new excuse in the meantime. $\endgroup$ – Thomas Klimpel Mar 11 '15 at 19:49
  • $\begingroup$ @ThomasKlimpel That's great! (Not the fact that you might find a new excuse, but that this was helpful :-)) $\endgroup$ – Juho Mar 11 '15 at 20:07
6
$\begingroup$

Although I don't know the name for such problem, I can show this problem is NP-hard.

For a triangle free graph, all equivalence classes must be a matching. The minimum number of equivalence classes that covers the graph equals the chromatic index of the graph.

According to this article, finding the chromatic index for a triangle free graph is NP-complete.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.