In this paper we are interested in decomposing a dihypergraph H = (V; E) into simpler dihypergraphs, that can be handled more efficiently. We study the properties of dihypergraphs that can be hierarchically decomposed into trivial dihypergraphs, i.e., vertex hypergraph. The hierarchical decomposition is represented by a full labelled binary tree called H-tree, in the fashion of hierarchical clustering. We present a polynomial time and space algorithm to achieve such a decomposition by producing its corresponding H-tree. However, there are dihypergraphs that cannot be completely decomposed into trivial components. Therefore, we relax this requirement to more indecomposable dihypergraphs called H-factors, and discuss applications of this decomposition to closure systems and lattices.
a recursive partitioning of the vertex set of the dihypergraph into smaller subhypergraphs or clusters, in the fashion of hierarchical clustering (see [Das16]). The H-decomposition is a way to represent a dihypergraph as a tree while preserving its vertices and arcs. The notion of a split of a dihypergraph is the principal tool we will use to achieve the H-decomposition. A split of a dihypergraph H = (V; E) is a partitioning of the dihypergraph’s vertices into two subsets (V1; V2) such that the arcs of H are the disjoint union of the arcs of the induced subhypergraphs H[V1], H[V2] and the bipartite dihypergraph H[V1; V2], i.e., for any e = (B; h) 2 E intersecting both V1 and V2, we have B V1 and h 2 V2 or vice versa. Clearly, there are dihypergraphs that cannot have a split. Our motivation is to study properties of dihypergraphs that can be H-decomposed into trivial dihypergraphs, i.e., hypergraphs with one vertex. The H-decomposition is represented by a full labelled binary trees called H-tree.
An application for our work arises from the decomposition of closure systems, or lattices. In particular, we wish to apply this decomposition to the problem of finding short representations of closure systems [Kha95, DNV19, Wil17]. Splitting lattices or closure systems is an old question and remains an active topic in several areas in mathematics and computer science. Among the common ways to split a lattice are the subdirect decomposition, the duplication (or doubling) of convex sets [BC02, VBDM15a], and other decompositions summarised in [GW99, GW12, Grä11, KVD05]. The former has been early considered by Birkhoff in [Bir44] where his representation theorem “Every algebra is a subdirect product of its subdirectly irreducible homomorphic images” is stated. Jipsen and Rose [JR92] summarize many results related to subdirect decomposition and give a list of subdirectly irreducible lattices. From the algorithmic point of view, several works can be found in [GW99, VBDM15b] where closure systems are represented with binary matrices (known as contexts) instead of dihypergraphs. Database theory community has however provided some decomposition schemes for dihypergraphs such as in [DLM92, SS96] or [Lib93], in view of database normalization. Other works on decomposition of dihypergraphs are considered in [BJJ03, GGPR98, AL17, PSSS20], where authors consider cuts or acyclic k-partitioning of dihypergraph. The split operation however is not a cut in general, while we seek for a full decomposition of a dihypergraph which is neither balanced nor acyclic.
In this paper, we present a polynomial time and space algorithm to achieve such a H-decomposition by producing a corresponding H-tree if it exists. However, there are dihypergraphs that cannot be completely decomposed into trivial components. Therefore, we relax this requirement to more indecomposable dihypergraphs called H-factors. This allows to extend the H-decomposition of dihypergraphs to closure systems and lattices.
The paper is structured as follows. In Section 2 we recall some definitions about dihypergraphs. In Section 3 we define the hierarchical decomposition of dihypergraphs, and its representation by a binary labelled tree. We also give a polynomial time and space algorithm to recognise dihypergraphs having a H-decomposition and produces the tree decomposition. Section 4 extends the H-decomposition to closure systems and provide some properties that can be useful for closure systems classification. 2
All the objects considered in this paper are finite. For a set V, we denote by 2V its powerset, and for n 2 N, we denote by [n] the set f1; : : : ; ng. Sometimes, We omit braces for sets, writing v1v2 : : : vn instead of fv1; : : : ; vng.
We mainly refer to papers [AL17, GLPN93] for terminology and definitions of dihypergraphs. A directed hypergraph (dihypergraph for short) H is a pair (V(H); E(H)) where V(H) is a set of vertices, and E(H) = fe1; : : : ; eng, n 2 N, a set of (hyper)arcs. An arc e 2 E(H) is a pair (B(e); h(e)), where ; 6= B(e) V is called the body of e and h(e) 2 V nB is the head of e. For simplicity, we shall write V, E and (B; h) for V(H), E(H) and (B(e); h(e)) respectively. An arc e = (B; h) is written as the set e = B [ fhg when no confusion can arise. If the body B of an arc is reduced to a single element b, we shall write (b; h) instead of (fbg; h). In this case, the arc (b; h) is unit. If a dihypergraph has only unit edges, it is a digraph.
Let H = (V; E) be a dihypergraph and U a subset of V. The subhypergraph H[U ] induced by U is the pair (U; E(H[U ])) where E(H[U ]) is the set of arcs of E contained in U , namely E(H[U ]) = fe 2 E j e U g. A bipartite dihypergraph is a dihypergraph in which the ground set can be partitioned into two parts (V1; V2) such that for any (B; h) 2 E, B V1 and h 2 V2 or B V2 and h 2 V1. We denote a bipartite dihypergraph by H[V1; V2]. The size of a dihypergraph H is written j H j and is given by j H j = j V j + Pe2E jB(e)j + 1. 3
In this section, we introduce a hierarchical decomposition (H-decomposition) of a dihypergraph as a recursive partition of the arcs into bipartite dihypergraphs, from which it can be fully recovered. We are interested first in the class of dihypergraphs that have a hierarchical decomposition. Given a dihypergraph H = (V; E), we define the partitioning operation called a split of H. Then we recursively apply the splitting operation until reaching trivial dihypergraphs. The H-decomposition of a dihypergraph H will be represented by a rooted binary tree, called H-tree.
We show that not all dihypergraphs can have such a H-decomposition into trivial dihypergraphs, and give a polynomial time and space algorithm which takes a dihypergraph as an input, and outputs a H-tree if it exists. Moreover, we relax the requirement of the H-decomposition into trivial dihypergraphs to H-factors which are indecomposable subhypergraphs of H. 3.1
Split operation First we define the split operation of a dihypergraph as follows. Definition 1 (split). Let H = (V; E) be a dihypergraph. A non-trivial bipartition (V1; V2) of the groundset V is a split of H, if for any e = (B; h) 2 E, B V1 or B V2.
A split (V1; V2) induces three subhypergraphs H[V1], H[V2] and a bipartite dihypergraph H[V1; V2] = (V1; V2; E12) where E12 = fe 2 E j e * V1 and e * V2g. Moreover, the arcs of H[V1], H[V2] and H[V1; V2] form a partition of E. Indeed, no arc is missed by a split. Intuitively, the split shows that H is fully described by two smaller distincts dihypergraphs H[V1] and H[V2] acting on each other through the bipartite dihypergraph H[V1; V2].
Example 1. Consider the dihypergraph H = (V; E) of Figure 1, with V = [7] and E = f(12; 3); (3; 1); (56; 2); (23; 7); (45; 6); (5; 7)g. The bipartition illustrated on the left separates V in two sets f1; 3g and f2; 4; 5; 6; 7g. It is not a split since the body of the arc (12; 3) intersects the two parts, and will be missed. The bipartition on the right V1 = f1; 2; 3g and V2 = f4; 5; 6; 7g is a split, with H[V1] = (f1; 2; 3g; f(12; 3); (3; 1)g), H[V2] = (f1; 2; 3g; f(45; 6); (5; 7)g), and H[V1; V2] = (f1; 2; 3g [ f4; 5; 6; 7g; f(56; 2); (23; 7)g).
1
2 3 5 7 6 4 1
2 3 5 7 6 4
Before giving a characterization of dihypergraphs having a split, we consider some special cases: – If the dihypergraph H is a digraph or has no arc. Then any bipartition of the ground set (any cut) is a split. – However, there are dihypergraphs that cannot have a bipartition that corresponds to a split. For example, any bipartition of the dihypergraph H = (f1; 2; 3g; f(12; 3); (13; 2)g) would miss an arc. For instance, if we consider the bipartition V1 = f1; 2g and V2 = f3g, then we capture (12; 3) but not (13; 2), i.e., H[V1] = (f1; 2g; ;), H[V2] = (f3g; ;), and H[V1; V2] = (f1; 2g [ f3g; f(12; 3)g).
In the following, we show that the dihypergraph’s connectivity is important
for the notion of a split. Given a dihypergraph H = (V; E), we define a
bodypath in H to be a sequence v1; e1; v2; :::; vk; ek; vk+1 of distinct vertices and arcs
of H such that: (
Observe that a body reduced to a singleton always satisfies condition of Definition 1. Thus, unit arcs have no impact on a split.
Proposition 1. A dihypergraph H has a split iff it is not body-connected. Proof. Suppose that H has a non trivial split (V1; V2), and let v 2 V1 and v0 2 V2. Assume the existence of a body-path v = v1; e1; v2; :::; vk; ek; vk+1 = v0. Such a body-path exists if there is i 2 [k] such that ei = (Bi; hi) and Bi \ V1 6= ; and Bi \V2 6= ;. But, the arc ei = (Bi; hi) cannot satisfy conditions of Definition 1. Then v; v0 are not body-connected and thus H is not body-connected.
Conversely, suppose that H is not body-connected and let C be a bodyconnected component of H. We show that (C; V nC) is a split. Let e = (B; h) 2 E. Since C is a body-connected component, either B \ C = ; or (V nC) \ B = ;. Hence (C; V nC) is a split. tu
It is important to note that body-connectivity is not inherited. That is, a subhypergraph induced by a body-connected component may not be bodyconnected. Consider the dihypergraph in Figure 1 with the split V1 = f1; 2; 3g and V2 = f4; 5; 6; 7g. Then 5 and 6 are body-connected in H but not in H[V2]. Therefore, body-connected components may be decomposed too. The main idea of the H-decomposition is to recursively apply the split operation until we reach a trivial dihypergraph. 3.2
H-tree of a dihypergraph Based on the split operation, we define the H-decomposition of a dihypergraph. We recursively split a dihypergraph into smaller dihypergraphs until we reach a trivial dihypergraph. This recursive decomposition can be conveniently represented by a full rooted binary tree T . An interior node of the tree corresponds to a split (V1; V2) whose children correspond to the H-decomposition of H[V1] and H[V2]. The leaves of the tree represent the ground set. Since the splits (V1; V2) and (V2; V1) are equivalent, the children of a node are not ordered. Definition 2 (H-tree). Let H = (V; E) be a dihypergraph, T be a full rooted binary tree. Then (T; ) is a H-tree of H if there exists a labelling map : T ! V [2E satisfying the following conditions: (i) (v) 2 V if v is a leaf of T , (ii) (v) E if v is an interior node (possibly (v) = ;), (iii) for any (B; h) 2 (v), elements of B are labels of leaves in the subtree of one child of v and h is the label of a leaf in the subtree of the other child. (iv) the set f (v) j v 2 T g is a full partition of V [ E and may contain the emptyset.
If such labelling exists we call the dihypergraph hierarchically decomposable (Hdecomposable for short), and H-indecomposable otherwise.
– H has no arcs. Here, any full rooted binary tree whose leaves are labelled by a permutation of V and any interior node by ; is a H-tree of H. – H is a digraph. It is the same as the previous case, except that an arc (b; h) will be in the label of the ancestor of the leaves labelled by b and h. However, there are also some dihypergraphs that cannot be H-decomposed.
; ;
; 1 Proof. Suppose that H is H-decomposable, and let (T; ) be a H-tree with root r. Let (Vl; Vr) be the split of V corresponding to r, i.e., Vl corresponds to the leaves of the left subtree of r and Vr to those of the right subtree. Then according to Proposition 1, H is not body-connected. tu
Now, we show that H-decomposability is hereditary, i.e., if a dihypergraph H has a H-tree then any of its subhypergraphs has a H-decomposition too. Proposition 3. Let H = (V; E) be a dihypergraph and U decomposable, so is H[U ].
V. If
H is HProof. Let H = (V; E) be a dihypergraph, U V and (T; ) a H-tree. We construct a subtree not necessarily induced by T which corresponds to a H[U ]tree. We start from the root r of T and apply the following operation for any interior node v: if the sets of leaves of the left child and those of the right one intersect both U , then keep v with label (v) = (v) \ E(H[U ]). Otherwise, there is a child of v whose set of leaves do not intersect U , in this case replace v by the child whose set of leaves intersects U . The obtained subtree has U as the set of leaves, and the set of labels of the internal nodes are exactly E(H[U ]). tu
The following theorem gives the strategy of the algorithm for recognizing which hypergraphs have a H-decomposition.
Theorem 1. Let H = (V; E) be a non body-connected dihypergraph and C a body-connected component of H. Then H is H-decomposable if and only if both H[C] and H[V nC] are H-decomposable.
Proof. The only if part directly follows from Proposition 3. Let us show the if part. Let C be a body-connected component of H and let (T1; 1) be a H[C]-tree and (T2; 2) a H[V nC]-tree. We consider a new tree (T; ) such that T has root r with left subtree T1 and right subtree T2. As for , we put (v) = 1(v) if v 2 T1, (v) = 2(v) if v 2 T2 and (r) = fe 2 E j e 2= E(H[C]) [ E(H[V nC])g. In words, (r) contains any arc which is not fully contained in C or V nC. It is clear that conditions (i), (ii), (iv) of Definition 2 are fulfilled for (T; ) as they are for (T1; 1), (T2; 2) and C [ V nC = V. Hence, we have to check (iii). Let e = (B; h) be an arc in (v). If B \ C 6= ;, then B C since C is a bodyconnected component of H. As e is not an arc of H[C], it follows that h 2 V nC. Dually, if B \ C = ;, then h 2 C since e is not in H[V nC]. Condition (iii) is satisfied and (T; ) is a H-tree. tu
Theorem 1 suggests a recursive algorithm which returns a H-tree for H if it is H-decomposable. If H is reduced to a vertex v, we output a tree which is a leaf with label v. Otherwise, we compute a body-connected component C of H if H is not body-connected. We label the corresponding node by the arcs of H[C; V nC], and we recursively call the algorithm on H[C] and H[V nC].
This strategy is formalized in Algorithm 1, whose correctness and complexity are studied in Theorem 2.
Theorem 2. Given a dihypergraph H = (V; E), Algorithm BuildTree computes a H-tree if it exists and returns FAIL otherwise in polynomial time and space in the size of H.
Proof. First, we show by induction on j V j that the algorithm returns a H-tree iff H is H-decomposable by. Clearly, if H is reduced to a vertex v, the algorithm returns a H-tree corresponding to a leaf with label v.
Now, assume that the algorithm is correct for dihypergraphs with j V j < n, n 2 N, and consider a dihypergraph H with j V j = n. Suppose H is Hdecomposable. By Proposition 1, H is not body-connected. Let C be a bodyconnected component of H. Inductively, the algorithm is correct for H[C] and Algorithm 1: BuildTree
Input: A dihypergraph H = (V; E)
Output: A H-tree, if it exists, FAIL otherwise 1 if H has one vertex then 2 create a new leaf r with (r) the unique vertex in H; 3 return r ; 4 else 5 6 7 H[V nC] since 1 jCj < n. From Theorem 1, we have that both H[C] and H[V nC] are H-decomposable. By induction the algorithm computes a H[C]-tree (T1; 1) and a H[V nC]-tree (T2; 2). Hence, the algorithm returns a labelled tree (T; ) with root r whose label is (r) = E n(E(H[C]) [ E(H[V nC])) and children T1 and T2. This tree satisfies all conditions to be a H-tree. Thus the algorithm computes a H-tree for any H-decomposable dihypergraph.
Now suppose H is not H-decomposable. We have two cases: 1. H is body-connected and the algorithm returns FAIL in Line 7. 2. H is not body-connected. The algorithm chooses a body-connected component C with 1 jCj < n. By Theorem 1, either H[C] or H[V nC] is H-indecomposable. Thus by induction, the algorithm will return FAIL for the input H[C] or H[V nC] in Lines 11-12. Since the algorithm stops, the output of the algorithm is FAIL.
Hence, the algorithm fails if the input dihypergraph H is H-indecomposable. We conclude that the algorithm returns a H-tree if and only if the input dihypergraph H is H-decomposable.
Now we show that the total time and space complexity of the algorithm are polynomial. The space required for the algorithm is bounded by the size of the dihypergraph and the size of the H-tree. As the size of the H-tree is bounded by O(j H j), the overall space is bounded by O(j H j).
The time complexity is bounded by the sum of the costs of all nodes (or calls) of the search tree. The number of calls is bounded by O(j V j), the size of the search tree. The cost of a call is dominated by the computation of a bodyconnected component of the input H. For this, we use union-find data structure of [TR84], which runs in almost linear time, i.e., O(j H j (j H j; j V j)) where (:; :) is the inverse Ackermann function. The almost linear comes from the fact that (j V j) 4 for any practical dihypergraph (see [TR84]). Thus the total time complexity is O(j V j(j H j (j H j; j V j)). tu
It is worth noticing, that the obtained H-tree by Algorithm 1 depends on the choice of a body-connected component in line 5. Thus, there may be several H-trees for a given dihypergraph. Figure 4 shows two possible H-trees for the dihypergraph H = (V; E) with V = [8] and E = f(12; 3); (23; 4); (34; 5); (56; 7); (67; 8)g. Then, a question arises: are all H-trees equivalently interesting? In particular, a balanced H-tree is a good candidate as the balancing is a common desirable property for decomposition trees to obtain efficient algorithms. As seen before, there are dihypergraphs that cannot have a split and thus a Hdecomposition into trivial hypergraphs. Such dihypergraphs are body-connected, and will be called irreducible H-factors (H-factors for short) in the rest of the paper. Now we describe a slight modification of Algorithm 1 to obtain a Hdecomposition of dihypergraphs into H-factors. Instead of returning FAIL in line 7 in Algorithm BuildTree, we replace it by the following:
7’ create a new leaf r with (r) = E and return r; In this section, we show that the H-decomposition introduced in the previous section can be applied to decompose closure systems when they are represented by dihypergraphs [Wil17, AL17].
We first recall definitions for closure systems and lattice theory [Grä11]. A partially ordered set L = (L; ) is a reflexive, anti-symmetric and transitive binary relation on a set L. For x; y 2 L, we say that x and y are comparable if x y or y x. An upper bound of x; y is an element u 2 L such that x u,
(6; 1) y u. If for any upper bound u0 6= u, u u0, then u is the join of x; y, written x _ y. Lower bounds and the meet x ^ y are defined dually. We say that L is a lattice if for any x; y 2 L, both x _ y and x ^ y exist. A meet-sublattice L0 of L is a lattice included in L such that for any x; y 2 L0, x ^ y 2 L0. It is a sublattice of L if moreover x _ y 2 L0.
A closure system F on a finite set V is a family of subsets of V which contains V and is closed under intersection, that is for any F1; F2 in the family F, F1 \ F2 also belongs to F. A subset F of V which is in F is called a closed set. It is well known that a closure system ordered by set containment is a lattice and that any lattice can be associated to a closure system [Grä11]. The projection or trace of a closure system F over U V, denoted F : U , is the closure system we obtain by intersecting each F 2 F with U , i.e., F : U = fF \ U j F 2 Fg. The direct product of two closure systems F1; F2 on disjoint V1; V2 is the pairwise union of their closed sets, that is F1 F2 = fF1 [ F2 j F1 2 F1; F2 2 F2g.
To compute the closure system associated to a dihypergraph H, we recall the forward chaining method. Let H be a dihypergraph and X V, we construct a chain of subsets of V, X = X0 X1 ::: Xk = XH, where Xi = Xi 1 [ fh j B Xi 1; (B; h) 2 Eg with i > 0. The subset XH is called a closed set. Note that a subset X of V is closed if for any arc (B; h); B X implies h 2 X. The family of closed sets FH = fXH j X Vg is a closure system. A closure system can be represented by several dihypergraphs.
Naturally, we wish to extend the H-decomposition of a dihypergraph H to a decomposition of the closure system FH, also called H-decomposition. The H-decomposition of FH is obtained from the H-decomposition of H, where the label of a node of its H-tree is replaced by the closure system associated to the dihypergraph induced by its subtree. The closure systems corresponding to leaves are the irreducible H-factors of the input closure system. Figure 6 illustrates the H-decomposition of the closure system associated to the H-decomposition of the dihypergraph in Figure 5.
Theorem 3. 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 2 FH then Fi = F \ Vi 2 Fi; i = f1; 2g. 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) H[V1; V2], then FH : Vi = Fi for i 2 f1; 2g. 4. If B V2 for any arc (B; h) of H[V1; V2], then FH : Vi = Fi for i 2 f1; 2g.
2 3 123 ; 1
1234 123 ; 2
123456 12356
12346 156 1236
1234 16 123
34 1 Proof. Consider a split (V1; V2) of H, F1 and F2 the closure systems corresponding to H[V1] and H[V2]. We will prove 1, 3 and 2. Items 3, 4 are similar. According to Theorem 3 1, any closure system is a subset of the product of its H-factors closure systems. So the idea is to compute in parallel F1 and F2 for every split (V1; V2) in the H-tree, and then use the dihypergraph H[V1; V2] to compute FH. But this strategy is expensive, since the size of F1 and F2 may be exponential in the size of FH. Indeed, take H with V = fu1; : : : ; un; zg and E = Sin=1f(ui; z); (z; ui)g. Then, (V nfzg; fzg) is a split of H with H[V nfzg] = (V nfzg; ;). Hence FV nfzg = 2V nfzg has exponential size, while FH = f;; Vg. Observe that this explosion cannot happen if F1 and F2 are traces of FH. 12 1 123 ; (a) 3 1 2
3 1 2
3 123 ; (b)
To conclude this section, we relate H-decomposition to the subdirect product decomposition. Consider the closure system FH in Figure 7(a) encoded by the unique dihypergraph H = (f1; 2; 3g; f(2; 1); (13; 2)g). It is known that it cannot be decomposed using the subdirect product. Clearly H is not body-connected and V1 = f1; 3g et V2 = f2g is the unique split where F1 = f;; 1; 3; 13g and F2 = f;; 2g are traces. But FH is not a sublattice of F1 F2, since (1; 3) 2 F1 F2 the upper bound of 1 and 3 is not preserved in FH. However, systems of Figure 7(b), (c) and (d) are subdirectly irreducible and H-factors too. Hence, we end the section with the following.
Corollary 1. Every closure system is a meet-sublattice of the direct product of its H-factors.
Proof. This follows from Theorem 3 (i) and the fact that a closure system is closed under intersection. tu 5
In this paper we studied a hierarchical decomposition for dihypergraphs based on a partitioning operation called a split. We gave a polynomial time and space algorithm to find such a decomposition if it exists. We also discussed application of this decomposition to closure systems and lattices.
For future research, we are interested in characterizing classes of closure systems which have a hierarchical decomposition. It seems that it is already the case for lower-bounded lattices, which include the widely studied Tamari lattices [Gey94, Mar92]. Another future application is the translation between representations of closure systems [Kha95, DNV19].
Acknowledgment Authors are grateful to the anonymous reviewers for their remarks and suggestions. [ADS86] [AL17] [BC02] [BDVG18] [Bir44] [BJJ03] [Das16] [DLM92] [DNV19] [Gey94] [GGPR98] [GLPN93] [Grä11] [GW99] [GW12]