Closure systems and their representations are essential in numerous fields of computer science. Among representations, dihypergraphs (or attribute implications) and meet-irreducible elements (reduced context) are widely used in the literature. Translating between the two representations is known to be harder than hypergraph dualization, a wellknown open problem. In this paper we are interested in enumerating the meet-irreducible elements of a closure system from a dihypergraph. To do so, we use a partitioning operation of a dihypergraph which gives a recursive characterization of its meet-irreducible elements. From this result, we deduce an algorithm which computes meet-irreducible elements in a divide-and-conquer way and puts the light on the major role of dualization in closure systems. Using hypergraph dualization, this strategy can be applied in output quasi-polynomial time to particular classes of dihypergraphs, improving at the same time previous results on ranked convex geometries.
Introduction
Closure systems play a major role in several areas of computer science and
mathematics such as database [
Due to the exponential size of a closure system, several compact
representations have been studied over the last decades [
directed hypergraphs (dihypergraphs for short) [
The second representation for a closure system is a (minimum) subset of
its elements from which it can be reconstructed. These elements are known as
meet-irreducible elements [
The problem of translating between these representations has been widely
studied in the literature [
In this paper we seek to push further the understanding of this problem,
based on previous works such as [
The paper is presented as follows. In Section 2 we recall definitions about
directed hypergraphs and closure systems. Section 3 introduces acyclic split of
a dihypergraph H and presents an example to illustrate our contribution. In
Section 4 we study the construction of the underlying closure system and we
give a characterization of its meet-irreducible elements. This characterization
suggests a recursive algorithm which computes meet-irreducible elements of H
in a divide-and-conquer way with acyclic splits, discussed in Section 5. We obtain
new classes of dihypergraphs for which computing meet-irreducible elements can
be done in output quasi-polynomial time using hypergraph dualization, thus
generalizing recent works on ranked convex geometries [
Preliminaries All the objects considered in this paper are finite. If V is a set, 2V denotes its powerset. For n ∈ N, we denote by [n] the set {1, . . . , n}. Sometimes we will denote by x1 . . . xn the set {x1, . . . , xn}.
We begin with notions on lattices and closure systems [
In this paper, we suppose that implicational bases are given as directed
hypergraphs. Directed hypergraphs are a convenient representation for attribute
implications of FCA, Horn clauses, functional dependencies [
The closure system associated to a dihypergraph H is obtained with the forward chaining algorithm. It starts from a subset X of V and constructs a chain X = X0 ⊆ X1 ⊆ · · · ⊆ Xk = XH such that for any i = 1, . . . , k we have Xi = Xi−1 ∪ {h | ∃(B, h) ∈ E s.t. B ⊆ Xi−1}. The operation (.)H is a closure operator, that is for any X, Y ⊆ V, we have X ⊆ XH, X ⊆ Y =⇒ XH ⊆ Y H and (XH)H = XH. A set X is closed if X = XH. Note that X is closed for H if and only if for any arc (B, h) ∈ E, B ⊆ X implies h ∈ X. We say that X satisfies an arc (B, h) if B ⊆ X =⇒ h ∈ X. The collection F(H) = {XH | X ⊆ V} of closed sets of H is a closure system. For clarity, we may write F instead of F(H). Our definition of a dihypergraph implies ∅ ∈ F, without loss of generality. 3
Acyclic split and illustration on an example
In this section we introduce acyclic splits and we illustrate our approach to
compute meet-irreducible elements from a dihypergraph on a toy example. Let V =
[
7 6 (a) A dihypergraph H 234567 23567
The idea is to split H into three subhypergraphs H[V1], H[V2] and H[V1, V2] as in [21]. However we use a restricted version of a split we call an acyclic split. A split is acyclic if for any arc (B, h) of H[V1, V2], B ⊆ V1 and h ∈ V2. A dihypergraph which does not have any acyclic split is indecomposable. A maximum subhypergraph of H which has no acyclic split is a c-factor (cyclic factor) of H. If a c-factor H0 of H is reduced to a vertex, i.e., H0 = ({x}, ∅), it is a singleton c-factor of H.
For instance in H, the bipartition V1 = {1, 2, 3}, V2 = {4, 5, 6, 7} is not a split because the body of (24, 6) has elements from both V1 and V2. If we fix V1 = {1, 2, 4, 6} and V2 = {3, 5, 7}, then the bipartition is a split but not acyclic since the arc (6, 5) goes from V1 to V2 and (57, 6) from V2 to V1. An acyclic split is V1 = {1, 2, 3, 4} and V2 = {5, 6, 7}. It induces the three subhypergraphs H[V1] = (V1, {(4, 3), (1, 4), (2, 3)}), H[V2] = (V2, {(6, 5), (57, 6)} and H[V1, V2] = (V, {(24, 6), (24, 7), (1, 5), (1, 7)}). Observe that H[V2] is indecomposable: the unique split of V1 is V01 = {5, 7} and V02 = {6}, which is not acyclic. Hence, H[V2] is a c-factor of H. Closure systems F1, F2 of H[V1] and H[V2] are given in Figure 2. Note that F is a meet-sublattice of F1 × F2.
234 23 1234 34 3
134 ; (a) F1, the closure lattice of H[V1] 56 5 567
7 ; (b) F2, the closure lattice of H[V2]
The splitting operation provides a partition of M(F) into two classes. The first class contains meet-irreducible elements of F1 to which we added V2. This is the case for example of 234567 and 567, which are the meet-irreducible elements 234 and ∅ of F1. The second class contains meet-irreducible which are inclusionwise maximal closed sets of F whose trace on V2 is meet-irreducible in F2. For instance, 235 and 345 are inclusion-wise maximal closed sets of F whose intersection with V2 rise 5, a meet-irreducible element of F2.
Thus, every meet-irreducible element of F belongs to exactly one of these two classes. Observe that any other F ∈ F cannot be part of M(F). As F ⊆ F1 × F2, every M ∈ M arise from the combination of some F1 ∈ F1 and F2 ∈ F2. Let F ∈ F be outside of those two class. If V2 ⊆ F , then F ∩ V1 cannot be meetirreducible in F1. In this case, covers of F ∩ V1 in F1 can be used to produce distinct covers of F in F. If however V2 * F , then covers of F ∩ V2 in F2 yield covers of F in F. In the case where F ∩ V2 is meet-irreducible in F2, there will be a closed set F1 in F1 such that F ∩ V1 ⊂ F1 and F1 ∪ (F ∩ V2) will be closed in F by assumption. This can be used to find another cover of F in F.
This characterization suggests to recursively find meet-irreducible elements
of F. If H is indecomposable, we computes M with known algorithms [
Thus, the steps we will follow are the following. Given a dihypergraph H and its closure system F, we will study the construction of F with respect to an acyclic split. This will lead us to a characterization of M. Recursively applying this characterization, we will get an algorithm to compute M from H. In this section, we show the construction of a closure system with respect to an acyclic split. We give a characterization of its closed sets and meet-irreducible elements M. Let H = (V, E) be a dihypergraph and (V1, V2) an acyclic split of H. Let F1, F2 be the closure systems associated to H[V1] and H[V2] respectively. Similarly, M1, M2 are their meet-irreducible elements. We show how to construct F from F1, F2 and H[V1, V2]. We begin with the following theorem from [21]: Theorem 1 (Theorem 3 of [21]). Let (V1, V2) be a split of H, F1 and F2 the closure systems corresponding to H[V1] and H[V2] respectively. Then, 1. If F ∈ FH then Fi = F ∩ Vi ∈ Fi, i = {1, 2}. Moreover, FH ⊆ F1 × F2. 2. If H[V1, V2] has no arc then FH = F1 × F2. 3. If B ⊆ V1 for any arc (B, h) of H[V1, V2], then FH : Vi = Fi for i ∈ {1, 2}. 4. If B ⊆ V2 for any arc (B, h) of H[V1, V2], then FH : Vi = Fi for i ∈ {1, 2}.
The first item states that F is a meet-sublattice of F. From item 2 we can
derive a characterization of meet-irreducible elements of the direct product F1 × F2.
This result has already been formulated in lattice theory, for instance in [
Proposition 1. Let H be a dihypergraph an (V1, V2) an acyclic split of H where H[V1, V2] has no arcs. Then M = {M1 ∪V2 | M1 ∈ M1}∪{M2 ∪V1 | M2 ∈ M2}. Proof. Let M ∈ M, i ∈ {1, 2} and Mi = M ∩ Vi. As M 6= V, Vi * M for at least one of i ∈ {1, 2}. Suppose it holds for V1 and V2. Then, there exists Mi0 ∈ Fi, such that Mi ≺ Mi0 in Fi. However, by Theorem 1, F = F1 × F2. Hence M1 ∪ M20 and M10 ∪ M2 belong to F. Furthermore they are incomparable and we have M ≺ M1 ∪ M20 and M ≺ M10 ∪ M2 which contradicts M ∈ M. Therefore, either V1 ⊆ M or V2 ⊆ M . Assume without loss of generality that V1 ⊆ M . Let M 00 be the unique cover of M in F. Then, V1 ⊆ M 00 and it follows that M2 ≺ M 00 ∩ V2 in F2. As M 00 is the unique cover of M in F, we conclude that M 00 ∩ V2 is the unique cover of M2 in F2 and M2 ∈ F2.
Let M1 ∈ M1 and consider M1 ∪ V2 ∈ F2. Let M10 be the unique cover of M1 in F1. As F = F1 × F2 by Theorem 1, we have that M1 ∪ V2 ≺ M10 ∪ V2 is in F. Let F be any closed set such that M1 ∪ V2 ⊂ F . We have F ∩ V2 = V2 and hence M1 ⊂ F ∩ V1. Since F = F1 × F2, we get F ∩ V1 ∈ F1. As M1 ≺ M10 in F1 and M1 ∈ M1, we conclude that M10 ⊆ F ∩ V1 and hence that M10 ∩ V2 ⊆ F . Therefore, M1 ∪ V2 ∈ M. Similarly we obtain M2 ∪ V1 ∈ M, for M2 ∈ M2. tu
Item 3 of Theorem 1 considers the case where the split is acyclic (as item 4 ). In particular, the proof of Theorem 1 shows that F2 ⊆ F in this case. Since F is a meet-sublattice of F1 × F2, and both F1, F2 appear as traces of F, we have that | F | ≥ | F1 | and | F | ≥ | F2 |. As F2 ⊆ F, for each F2 ∈ F2, it may exists several closed sets of F1 which extend F2 to another element of F. Definition 1. Let H be a dihypergraph with acyclic split (V1, V2). Let F1 ∈ F1, F2 ∈ F2. We say that F1 ∪ F2 is an extension of F2 if it belongs to F. We denote by Ext(F2) the set of extensions of F2, namely Ext(F2) = {F ∈ F | F ∩V2 = F2}.
We denote by Ext(F2) : V1 the set of closed sets of F1 which make extensions of F2. Hence, any closed set F of F can be seen as the extension of some F2 ∈ F2 so that F results from the union of extensions of closed sets in F2: F =
[ Ext(F2)
F2∈F2 Extensions of F2 ∈ F2 can be characterized using H[V1, V2] as follows. Lemma 1. Let F1 ∈ F1, F2 ∈ F2. Then F1 ∪ F2 is an extension of F2 if and only if for any arc (B, h) in H[V1, V2], B ⊆ F1 implies h ∈ F2.
Proof. We begin with the only if part. Let F1 be a closed set of F1 such that F1 ∪ F2 is an extension of F2 and let (B, h) ∈ H[V1, V2]. If B ⊆ F1, then it must be that h ∈ F2 since otherwise we would contradict F1 ∪ F2 ∈ F.
We move to the if part. Let F1 be a closed set of F1 and F2 a closed set of F2 such that for any arc (B, h) ∈ H[V1, V2], B ⊆ F1 implies h ∈ F2. We have to show that F1 ∪ F2 is closed. Let (B, h) be an arc of H. As (V1, V2) is an acyclic split of V, we have two cases for (B, h): either (B, h) is in H[V1, V2] or it is not. In the second case, assume it is in H[V1]. As B ⊆ F1 ∪ F2, we have B ⊆ F1. Furthermore, F1 is closed for H[V1]. Hence, h ∈ F1 ⊆ F1 ∪ F2. The same reasoning can be applied if (B, h) is in H[V2]. Now assume (B, h) is in H[V1, V2]. We have that B ⊆ V1 by definition of an acyclic split. In particular we have B ⊆ F1 which entails h ∈ F2 by assumption. In any case, F1 ∪F2 already contains h for any arc (B, h) such that B ⊆ F1 ∪ F2 and F1 ∪ F2 is closed. tu
Observe that for the particular case F2 = V2, we have Ext(V2) : V1 = F1 because any arc (B, h) of H[V1, V2] satisfies h ∈ V2. A consequence of Lemma 1 is that the extension is hereditary, as stated by the following lemma. Lemma 2. Let F1 ∈ F1, F2 ∈ F2. If F1 ∪ F2 is an extension of F2, then for any closed set F10 of F1 such that F10 ⊆ F1, F10 ∪ F2 is also an extension of F2. Proof. Let F1 ∈ F1, F2 ∈ F2 such that F1 ∪ F2 ∈ F. Let F10 ∈ F1 such that F10 ⊆ F1. As F1 ∪ F2 is an extension of F2, for any arc (B, h) of H[V1, V2] such that B ⊆ F1, we have h ∈ F2 by Lemma 1. Since F10 ⊆ F1, this condition holds in particular for any arc (B, h) of H[V1, V2] such that B ⊆ F10 ⊆ F1. Applying Lemma 1, we have that F10 ∪ F2 is closed. tu
As F is a meet-sublattice of F1 × F2 by Theorem 1, it follows from Lemma 2 that for any F2 ∈ F2, the set Ext(F2) : V1 is an ideal of F1. Thus, it is uniquely determined by its maximal elements. They are inclusion-wise maximal closed sets of F1 satisfying the condition of Lemma 1.
Example 1. We consider the introductory example H and the acyclic split V1 = {1, 2, 3, 4} and V2 = {5, 6, 7}. We have for instance Ext(7) = {7, 37, 237, 347} which corresponds to the ideal {∅, 3, 23, 24} of F1 illustrated on the left of Figure 2 representing F1.
Now we are interested in the characterization of meet-irreducible elements M of F. The strategy is to identify for each F2 ∈ F2, which closed sets of Ext(F2) are meet-irreducible elements of F.
Proposition 2. Let F = F1 ∪ F2 ∈ F. Let F20 ∈ F2 such that F2 ≺ F20. Then F20 ∪ F1 is closed in F and F ≺ F20 ∪ F1 in F.
Proof. Let F = F1 ∪ F2 ∈ F. Let F20 ∈ F2 such that F2 ≺ F20. As F1 ∪ F2 is an extension of F2, for every arc (B, h) of H[V1, V2] such that B ⊆ F1, we have h ∈ F2 ⊆ F20 by Lemma 1. Therefore, F1 ∪ F20 is an extension of F 0. 2
Now we show that F1 ∪ F20 is a cover of F . Let F 00 ∈ F such that F ⊆ F 00 ⊆ F1 ∪ F 0. As F ∩ V1 = F1 = (F1 ∪ F20) ∩ V1, we have that F 00 ∩ V1 = F1. Recall 2 from Theorem 1 that F ⊆ F1 × F2. Therefore F 00 ∩ V2 is a closed set of F2 and F2 ⊆ F 00 ∩ V2 ⊆ F 0. As F2 ≺ F20 in F2, we have either F2 = F 00 ∩ V2 or 2 F20 = F 00 ∩ V2. Consequently, F 00 = F or F 00 = F1 ∪ F20 which entails F ≺ F1 ∪ F20 in F, concluding the proof. tu
A consequence of this proposition is that for any F2, F20 ∈ F2 such that F2 ⊆ F20, one has Ext(F2) : V1 ⊆ Ext(F20) : V1. In particular, if F2 ≺ F20 in F2, then each extension F of F2 is covered by the unique extension F 0 of F20 such that F ∩ V1 = F 0 ∩ V1. This leads us to the following lemmas.
Lemma 3. Let F2 ∈ F2, F2 6= V2 and F1 ∈ F1 such that F1 ∪ F2 is a nonmaximal extension of F2. Then F1 ∪ F2 ∈/ M.
Proof. Let F2 ∈ F2, F2 6= V2 and F1 ∈ F1 such that F1 ∪ F2 is a non-maximal extension of F2. As F2 6= V2, there exists at least one closed set F20 ∈ F2 such that F2 ≺ F 0. By Proposition 2 we have that F1∪F2 ≺ F1∪F20 in F. Furthermore, 2 F1 ∪ F2 is not a maximal extension of F2. Therefore, there exists a closed set F 0 1 in F1 such that F1 ≺ F10 and F10 ∪ F2 ∈ F. As F ⊆ F1 × F2 by Theorem 1 and extension is hereditary by Lemma 2, it follows that F1 ∪ F2 ≺ F10 ∪ F2 in F with F1 ∪ F20 6= F10 ∪ F2. Therefore F1 ∪ F2 is not a meet-irreducible element of F. tu Lemma 4. Let F2 ∈ F2 such that F2 6= V2 and F2 ∈/ M2. Then F ∈/ M for any F ∈ Ext(F2).
Proof. Let F2 ∈ F2 such that F2 6= V2 and F2 ∈/ M2. Let F ∈ Ext(F2) and F1 = F ∩V1. As F2 ∈/ M2, it has at least two covers F 0, F200 in F2. By Proposition 2 2, it follows that both F20 ∪F1 and F200 ∪F1 are covers of F in F. Hence F ∈/ M. tu
These lemmas suggest that meet-irreducible elements of F arise from maximal extensions of meet-irreducible elements of F2. They might also come from meetirreducible extensions of V2 since Ext(V2) : V1 = F1. As V2 has no cover in F2, Proposition 2 cannot apply. These ideas are proved in the following theorem which characterize meet-irreducible elements M of F.
Theorem 2. Let H = (V, E) be a dihypergraph with an acyclic split (V1, V2). Meet-irreducible elements M of F are given by the following equality:
M = {M1 ∪ V2 | M1 ∈ M1} ∪ {F ∈ max⊆(Ext(M2)) | M2 ∈ M2} Proof. First we show that {M1 ∪V2 | M1 ∈ M1} ⊆ M. Let M1 ∈ M1. By Lemma 1, we have that M1 ∪ V2 ∈ F, as h ∈ V2 for any (B, h) in H[V1, V2]. Let F 0, F 00 be two covers of M1 ∪ V2 in F. First, observe that F 0 and F 00 differ from M1 ∪ V2 only in V1 as they both contain V2. By Theorem 1, F ⊆ F1 × F2, so F 0 ∩ V1 and F 00 ∩ V1 are closed sets of F1. Furthermore Ext(V2) : V1 = F1 by Lemmas 2 and 1. Therefore, both F 0 ∩ V1 and F 00 ∩ V1 cover M1 in F1. Since M1 is a meet-irreducible element of F1, we conclude that F 0 = F 00 and M1 ∪ V2 ∈ M.
Next, we prove that {F ∈ max⊆(Ext(M2)) | M2 ∈ M2} ⊆ M. Let M2 ∈ M2 and F ∈ max⊆(Ext(M2)) with F = F1 ∪ M2. Since M2 ∈ F2, it has a unique cover M20 in F2. By Proposition 2, we get F ≺ M20 ∪ F1 in F. Let F 00 ∈ F such that F ⊂ F 00. Recall that F ⊆ F1 × F2 by Theorem 1, so that F 00 ∩ V1 ∈ F1 and F 00 ∩ V2 ∈ F2. Furthermore, F ∈ max⊆(Ext(M2)), therefore F ⊂ F 00 implies that M2 ⊂ F 00 ∩ V2 and hence that M20 ⊆ F 00 ∩ V2 as M2 ∈ F2. Since F1 ⊆ F 00 ∩ V1, we get F ≺ M20 ∪ F1 ⊆ F 00 and F ∈ M as it has a unique cover.
Now we prove the other side of the equation. Let M ∈ M. As F ⊆ F1 × F2, M ∩ V2 ∈ F2 and we can distinguish two cases. Either M ∩ V2 = V2 or M ∩ V2 ⊂ V2. Let us study the first case and let M1 = M ∩ V1. Let M 0 be the unique cover of M in F. We show that M10 = M 0 ∩ V1 is the unique cover of M1 in F1. By Theorem 1 and Lemma 2, we have that M1 ≺ M10 in F1. Let F1 be any closed set of F1 with M1 ⊂ F1. Recall that Ext(V2) : V1 = F1 by Lemmas 1 and 2. Hence F1 ∪ V2 is closed and M ⊆ F1 ∪ V2. As M ∈ M , we also deduce M 0 ⊆ F1 ∪ V2. Therefore, M10 ⊆ F1, and M10 must be the unique cover of M1 in F1. So, M1 ∈ M1 and for any M ∈ M such that V2 ⊆ M , we have M ∈ {M1 ∪ V2 | M1 ∈ M1}.
Now assume that M ∩ V2 ⊂ V2. Let M1 = M ∩ V1 and M2 = M ∩ V2. Then by contrapositive of Lemma 3 we have that M ∈ max⊆(Ext(M2)) as M2 6= V2. Similarly we get M2 ∈ M2 by Lemma 4. tu
This theorem hints a strategy to compute meet-irreducible elements in a recursive manner, using a hierarchical decomposition of H with acyclic splits, as proposed in the next section. 5
Recursive application of acyclic splits In this section, we discuss an algorithm to compute M from a dihypergraph H based on Theorem 2. First, note that we have both | M | ≥ | M1 | and | M | ≥ | M2 |. Furthermore, each M ∈ M arise from a unique element of M 0 ∈ M1 ∪ M2, and each M 0 ∈ M1 ∪ M2 is used to construct at least one new meet-irreducible element M ∈ M. Therefore, we deduce an algorithm whose output is precisely M, where each M ∈ M is given only once. Furthermore, the space needed to store intermediate solutions is bounded by the size of the output M which prevents an exponential blow up during the execution. The algorithm proceeds as follows. For c-factors of H, we use algorithms such as in [19] to compute M. When cfactors are singletons, the unique meet-irreducible to find is ∅ and hence no call to other algorithm is required. Otherwise, we find an acyclic split (V1, V2) of H and we recursively call the algorithm on H[V1] and H[V2]. Then, we compute M using M1, M2 and Theorem 2.
Computing M from M1, M2 requires to find maximal extensions of every meet-irreducible element M2 ∈ M2. We will show that finding maximal extensions of a closed set is equivalent to a dualization problem in closure systems. First, we state the extension problem:
Problem: Find Maximal Extensions with Acyclic Split (FMEAS) Input: A triple H[V1], H[V2], H[V1, V2] given by an acyclic split of a dihypergraph H, meet-irreducible elements M1, M2, and a closed set F2 of H[V2].
Output: The maximal extensions of F2 in F, i.e., max⊆(Ext(F2)).
Let B+, B− be two antichains of F. The dualization in lattices asks if two antichains B−, B+ are dual in F, that is if
# B+ ∪ " B− = F and " B− ∩ # B+ = ∅.
Note that B− and B+ are dual if either B+ = max⊆{F ∈ F | F ∈/ " B−} or B− = min⊆{F ∈ F | F ∈/ # B+}. If F is given, the question can be answered in polynomial time. In our case however, F is implicitly given by M and H. More precisely we use the next generation problem:
Problem: Dualization with Dihypergraph and meet-irreducible (DMDual) Input: A dihypergraph H = (V, E), the meet-irreducible elements M of F, and an antichain B− of F.
Output: The dual antichain B+ of B−.
This problem has been introduced in [
We show that FMEAS and DMDual are equivalent under polynomial reduction. First, we relate maximal extensions of a closed set with dualization. Let F2 ∈ F2. Recall that Ext(F2) : V1 is an ideal of F1. Hence, the antichain max⊆(Ext(F2) : V1) has a dual antichain B−(F2) in F1, i.e., B−(F2) = min⊆{F1 ∈ F1 | F1 ∈/ Ext(F2) : V1}.
Proposition 3. Let F2 ∈ F2, and F1 ∈ F1. Then, F1 ∈ B−(F2) if and only if F1 ∈ min⊆{BH[V1] | (B, h) ∈ H[V1, V2], h ∈/ F2}.
Proof. We show the if part. Let F1 ∈ min⊆{BH[V1] | (B, h) ∈ H[V1, V2], h ∈/ F2}. We show that for any closed set F10 ⊆ F1 in F1, F10 contributes to an extension of F2. It is sufficient to show this property to the case where F10 ≺ F1 as Ext(F2) : V1 is an ideal of F1. Hence consider a closed set F10 in F1 such that F10 ≺ F1. Note that such F10 exists since ∅ ∈ F1 and no arc (B, h) in H has B = ∅ so that ∅ ⊂ BH[V1] for any arc (B, h) of H[V1, V2] such that h ∈/ F2. Then, by construction of F 0, for any (B, h) in H[V1, V2] such that 1 h ∈/ F2, we have BH[V1] * F10. As (.)H[V1] is a closure operator, it is monotone and BH[V1] * F 0 H[V1] = F10 entails B * F10 for any such arc (B, h). Therefore 1 F10 ∈ Ext(F2) : V1 and F1 ∈ B−(F2).
We prove the only if part. We use contrapositive. Assume F1 ∈/ min⊆{BH[V1] | (B, h) ∈ H[V1, V2], h ∈/ F2}. Then we have two cases. First, for any arc (B, h) in H[V1, V2] such that h ∈/ F2, BH[V1] * F1. As (.)H[V1] is a closure operator, it is monotone, and since F1 is closed in F1, we have B * F1 and F1 ∈ Ext(F2) : V1 by Lemma 1. Hence F1 ∈/ B−(F2). In the second case, there is an arc (B, h) with h ∈/ F2 in H[V1, V2] such that BH[V1] ⊆ F1 which implies F1 ∈/ Ext(F2) : V1. If BH[V1] ⊂ F1, then clearly F1 ∈/ B−(F2) as BH[V1] ∈ F1 and BH[V1] ∈/ Ext(F2) : V1. Hence, assume that F = BH[V1]. Since F1 ∈/ min⊆{BH[V1] | (B, h) ∈ H[V1, V2], h ∈/ F2} by hypothesis, there exists another arc (B0, h0) ∈ E(H[V1, V2]) such that h ∈/ F2 and B0 H[V1] ⊂ F1. Hence B0 H[V1] ∈/ Ext(F2) : V1 and F1 ∈/ B−(F2) as it is not an inclusion-wise minimum closed set which does not belong to Ext(F2) : V1. tu
Observe that for any F2 ∈ F2, B−(F2) can easily be computed using H[V1, V2] and Lemma 1. Therefore we prove the following theorem.
Theorem 3. FMEAS and DMDual are polynomially equivalent. Proof. First we show that DMDual is harder than FMEAS. Let H = (V, E) be a dihypergraph, and (H[V1], H[V2], H[V1, V2], M1, M2, F2) be an instance of FMEAS. By Proposition 3, finding max⊆(Ext(F2)) amounts to find the dual antichain of B−(F2) = min⊆{BH[V1] | (B, h) ∈ H[V1, V2], h ∈/ F2} in F1. Note that B−(F2) can be computed in polynomial time in the size of H[V1] and | B−(F2)| ≤ | E(H[V1, V2])|. Therefore, the instance of FMEAS reduces to the instance (H[V1], M1, B−(F2)) of DMDual.
Now we show that FMEAS is harder than DMDual. Let (H, M, B−) be an instance of DMDual. Let z be a new gadget vertex and consider the bipartite dihypergraph H[V, {z}] = (V ∪{z}, {(B, z) | B ∈ B−}). Let Hnew = H ∪ H[V, {z}]. Clearly, Hnew has an acyclic split (V, {z}) such that Hnew[V] = H, Hnew[{z}] = ({z}, ∅) and Hnew[V, {z}] = H[V, {z}]. The closure system associated to Hnew[{z}] has only 2 elements: its unique meet-irreducible element ∅ and {z}. We obtain an instance FMEAS where the input is H, Hnew[{z}], H[V, {z}], M, {∅} and where the closed set of interest is ∅. Moreover this reduction is polynomial in the size of (H, M, B−) as we create a unique new element and | B− | arcs. According to Proposition 3, maximal extensions of ∅ are given by the antichain dual to B−(∅) = min⊆{BH | (B, z) ∈ H[V, {z}]}. However, we have B−(∅) = B−, so that maximal extensions of ∅ are precisely elements of the dual antichain B+ of B−. tu
We can deduce a class of dihypergraphs where our strategy can be applied to
obtain meet-irreducible elements in output quasi-polynomial time. Let us assume
that H can be decomposed as follows. Its c-factors are singletons. If H is not
itself a singleton, it has an acyclic split (V1, V2) with H[V1] = (V1, ∅). Hence,
DMDual reduces to hypergraph dualization and can be solved in output-quasi
polynomial time using the algorithm of [
The closure system represented by a dihypergraph H is a ranked convex geometry if there exists a full partition V1, . . . , Vn, of V such that H[Vi] = (Vi, ∅) for any 1 ≤ i ≤ n and for any arc (B, h) in H there is a j < k such that B ⊆ Vj and h ∈ Vj+1. All c-factors of H are singletons. Choosing the acyclic split (Vi, Sn
j=i+1 Vj ) at the i-th step of the algorithm yields a decomposition which satisfies conditions of the previous paragraph. 6
Conclusion In this paper we investigated the problem of finding meet-irreducible elements of a closure system represented by a dihypergraph. In general, the complexity of this problem is unknown and harder than hypergraph dualization. Using a partitioning operation called an acyclic split on the dihypergraph, we gave a characterization of its associated meet-irreducible elements. Acyclic splits lead to a recursive algorithm to find meet-irreducible elements from a dihypergraph.
With our algorithm, we reach new classes of dihypergraphs for which
meetirreducible elements can now be computed in output quasi-polynomial time. In
particular, we improve previous results on ranked convex geometries [
ACM (JACM) 27, 4 (1980), 664–674. [19] Mannila, H., and Räihä, K.-J. The design of relational databases.
Addison-Wesley Longman Publishing Co., Inc., 1992. [20] Markowsky, G. Primes, irreducibles and extremal lattices. Order 9, 3 (1992), 265–290. [21] Nourine, L., and Vilmin, S. Hierarchical decompositions of dihypergraphs. arXiv preprint arXiv:2006.11831 (2020). [22] Wild, M. Computations with finite closure systems and implications. In International Computing and Combinatorics Conference (1995), Springer, pp. 111–120. [23] Wild, M. The joy of implications, aka pure horn formulas: mainly a survey.
Theoretical Computer Science 658 (2017), 264–292.