Enumerating the Irreducible Closed Sets of an Acyclic Implicational Base of Bounded Degree

Finite closure systems appear in disguise in several areas of mathematics and computer science, including database theory [29, Chapter 13], Horn logic [12, Chapter 6], or lattice theory [13, Chapter 2], to mention but a few.

A closure system is a family of subsets of some finite ground set being closed by intersection and containing the ground set. The study of the various representations of closure systems and the algorithmic task of translating between them have received lots of attention in these respective fields, and have been the topic of the Dagstuhl Seminar 14201 [1]. Most importantly, the translation task we consider in this paper is known for being a considerable generalization of the notorious and widely open hypergraph dualization problem, while also not being known to be intractable, contrary to analogous other natural generalizations such as lattice dualization [26, 4, 14]. We refer the reader to the surveys [39, 7, 33] for more information on this topic.

Among the several representations of closure systems, two of them occupy a central role, namely, irreducible closed sets and implicational bases, whose formal definitions are postponed to Section 2. Informally, irreducible closed sets are elementary sets of the closure system from which every other can be recovered. On the other hand, implicational bases are sets of implications of the form $A\to B$, where $A$, the premise, and $B$, the conclusion, are subsets of the ground set. As noted in [28], these two representations are generally incomparable in size and usefulness. Notably, there exist instances where the minimum cardinality of an implicational bases is exponential in the number of irreducible closed sets, and vice versa. Moreover, the computational complexity of some algorithmic tasks such as reasoning, abduction, or recognizing lattice properties can differ significantly depending on the representation at hand [25, 3, 29]. These observations motivate the problem of translating between the two representations, in which one representation is given, and the other is to be computed. In this extended abstract, a focus is made on the problem of enumerating irreducible closed sets, denoted by ICS$\cdot$Enum; the dual problem of constructing the implicational base is only addressed in the long version of this work.

Because of the possible exponential gap between the sizes of the two representations, input sensitive complexity is not a meaningful efficiency criterion when analyzing the performance of an algorithm solving ICS$\cdot$Enum. Instead, the framework of algorithmic enumeration in which an enumeration algorithm has to list without repetitions a set of solutions, is usually adopted. The complexity of an algorithm is then analyzed from the perspective of output-sensitive complexity, which estimates the running time of the algorithm using both input and output sizes. In that context, an algorithm is considered tractable when it runs in output-polynomial time, that is, if its execution time is bounded by a polynomial in the combined sizes of the input and the output. This notion can be further constrained to guarantee some regularity in the enumeration. Namely, we say that an algorithm runs in incremental-polynomial time if it outputs the $i^{\text{th}}$ solution in a time which is bounded by a polynomial in the input size plus $i$. It is said to run with polynomial delay if the time spent before the first output, after the last output, and between consecutive outputs is bounded by a polynomial in the input size only. We refer the reader to [24, 35] for more details on enumeration complexity.

In this work, we investigate acyclic convex geometries, a particular class of closure systems. They are the convex geometries – closure systems with the anti-exchange property – that admit an implicational base with acyclic implication-graph. Acyclic convex geometries have been extensively studied [23, 37, 8, 34, 15]. Even in this class though, the problem ICS$\cdot$Enum was shown in [15] to be harder than distributive lattices dualization, a generalization of hypergraph dualization. On the other hand, the authors in [15] show that if, in addition to acyclicity, the implication graph admits a rank function, then the problem can be solved using hypergraph dualization. Using this result, they derive a tractable algorithm for so-called ranked convex geometries admitting an implicational base of bounded premise size. It should be noted that, even under these restrictions, the problem generalizes the one of enumerating all maximal independent sets of a graph (in fact of hypergraphs of bounded edge size) a central and notorious problem in enumeration [36, 24]. These results have then been extended to a more general setting in [32]. Other related results in the literature include the work [5] which deals with $k$-meet-semidistributive lattices, and closure systems of bounded Caratheodory number, see e.g., [39].

In this paper, we continue the line of research of characterizing tractable cases of acyclic convex geometries, by identifying for which parameters $k$ one can derive tractable algorithms for ICS$\cdot$Enum for fixed values of $k$. We note that in this research, finding an algorithm running in quasi-polynomial time should already be considered a success, since no sub-exponential time algorithms are known to date. We focus on the degree, which is defined as the maximum number of implications in which an element participates, and its two obvious relaxations which are the premise- and conclusion-degree; these parameters are defined in Section 2. The principal message of this work is that bounding one of these two relaxed notions of degree suffices to provide not only quasi-polynomial but polynomial algorithms for the translation. More specifically, as the first of our two main theorems, we obtain the following, whose quantitative formulation is postponed to Sections 4 and 5.

Our algorithms for acyclic convex geometries of bounded degree rely on several steps which combine structure and enumeration techniques. We give a rough description which highlight the techniques used, and refer to the appropriate sections for more details.

First, we use the fact that each irreducible closed set is attached to an element of the ground set, and that this element is unique in convex geometries; this is detailed in Section 2. Then, leveraging from acyclicity, our algorithm relies on a sequential procedure which consists of enumerating, incrementally and in a top-down fashion according to a topological ordering $x_1,\mathrm{\dots },x_n$ of the elements of the ground set, all the irreducible closed sets attached to $x_i$. This step can be seen as enumerating the irreducible closed set attached to $x_i$ with additional information as an input, namely, the irreducible closed sets of ancestor elements. Finally, it remains to solve this later task, which we can do either by brute forcing minimal transversals of a carefully designed hypergraph in case of bounded conclusion-degree, or performing a solution graph traversal in case of bounded premise-degree. In the end, the resulting algorithms run in incremental-polynomial time, where the dependence in the number of solutions principally arises from the sequential top-down procedure.

Let us note that Theorem 1 also has implications on the dual problem of constructing an implicational base of minimum cardinality. Namely it allows us to obtain the following result whose description is detailed in the long version of this work [16] and included here for the reader familiar with closure systems.

We note that in this direction, our algorithm is (input) polynomial thanks to the fact that the output has polynomial cardinality because of the bounded degree.

The remainder of the paper is organized as follows. Section 2 introduces the concepts and notations used throughout the paper. Section 3 presents the top-down approach that we use as the key ingredient in our algorithms. Sections 4 and 5 are devoted to proving Theorem 1 in the respective cases of bounded conclusion- and premise-degree. In Section 6 we discuss possible generalizations and open problems related to the current work, and also argue that our running times cannot be improved to polynomial delay using the standard framework of flashlight search.

Due to space constraints, the proofs of our different statements are not included in the present extended abstract: the interested reader is referred to [16] for more details.

All the objects we consider in this paper are finite. If $X$ is a set, $𝒫(X)$ is its powerset. The size of $X$ is denoted $|X|$. A set system, or hypergraph, over a ground set $X$ is a pair $(X,ℱ)$ where $ℱ$ is a (non-empty) collection of subsets of $X$, that is $ℱ\subseteq 𝒫(X)$. Its size is $|X|+|ℱ|$; note that the binary length of any standard encoding of a hypergraph is polynomially related to its size. Thus, for simplicity, we shall consider this measure for families as input sizes in the different problems we will consider. If $X$ is clear from the context, we may identify $ℱ$ with $(X,ℱ)$. In examples, if there is no ambiguity, we may write a set as the concatenation of its elements, for instance $123$ instead of $\{1,2,3\}$. Similarly, to avoid cumbersome notations, we sometimes withdraw brackets when dealing with singletons, e.g., we may write say $\varphi (x)$ instead of $\varphi (\{x\})$.

We describe the general sequential procedure that we use to solve ICS$\cdot$Enum. We use a similar approach to tackle the dual problem of constructing the implicational base in the long version of this work [16]. Intuitively, it consists in enumerating, incrementally and in a top-down fashion according to a topological ordering $x_1,\mathrm{\dots },x_n$ of the implicational base, all the irreducible closed sets attached to $x_i$.

Recall that the ancestors of an element $x$ in an acyclic implicational base are the elements that participate in a path of implications to $x$, and which can be identified in polynomial time; see Section 2. More formally, we show that ICS$\cdot$Enum reduces to the following version of ACS$\cdot$Enum in which we are given ancestors’ irreducible closed sets as additional information.

Clearly, an algorithm for ACS$\cdot$Enum can be used to solve ACS+A$\cdot$Enum, while the reverse may not be true. We argue that by iteratively using an algorithm for ACS+A$\cdot$Enum on a maximal element of the implicational base among those that have not been selected yet, we obtain an algorithm for ICS$\cdot$Enum. Note that the base case corresponds to computing the irreducible closed set of maximal elements $x$ verifying $\mathrm{irr}(x)=\{X\setminus \{x\}\}$. Moreover, this procedures preserves incremental-polynomial bounds. In terms of difficulty, ACS+A$\cdot$Enum may thus be seen as standing as an intermediate problem between ACS$\cdot$Enum and ICS$\cdot$Enum in acyclic convex geometries. More formally, we obtain the following.

$◀$

We note that an analogous statement to the one in Theorem 6 holds by relaxing the required and obtained time bounds to output-polynomial times. On the other hand, improving the complexity of an algorithm for ACS+A$\cdot$Enum to polynomial delay (or even input-polynomial as we will provide later for the case of bounded conclusion-degree) does not generally ensure polynomial delay (or incremental-linear) for ICS$\cdot$Enum, since the size of an instance of ACS+A$\cdot$Enum grows with the number of already obtained solutions for ICS$\cdot$Enum, which typically becomes exponential in the size of the implicational base.

Further limitations related to the top-down approach – in particular on the hardness of ACS$\cdot$Enum on implicational bases of height at most two – are discussed in the long version of this work [16]. Nevertheless, we shall argue in the remaining of the paper that this approach yields tractable algorithms when bounding structural parameters such as the premise- and conclusion-degree.

We show that the top-down approach successfully provides an incremental-polynomial time algorithm for ICS$\cdot$Enum whenever the implicational base has bounded conclusion-degree, proving one of the two cases of Theorem 1.

In the following, let us consider an instance of ACS+A$\cdot$Enum, i.e., we fix some acyclic implicational base $(X,\mathrm{\Sigma })$, an element $x\in X$, and assume that we are given $\mathrm{irr}(y)$ for all ancestors $y$ of $x$ in $\mathrm{\Sigma }$. Let us consider the hypergraph defined by

The intuition behind the following lemma is that, in order to get an irreducible closed set attached to $x$, one should remove at least one element $a$ in the premise of each implication having $x$ in the conclusion, which can be done by considering the intersection with an irreducible closed set attached to $a$. Recall that $𝒮(T)$ denotes the family of irreducible selections; see Section 2.

$◀$

Note that, by definition, the number of edges in ${\mathscr{H}}_x$ is exactly $\mathrm{cdeg}(x)$, which is at most $\mathrm{cdeg}(\mathrm{\Sigma })$. Moreover, since the ground set of ${\mathscr{H}}_x$ is a subset of the ancestors of $x$, the selections of Lemma 7 are part of the input we consider for ACS+A$\cdot$Enum. By brute-forcing the irreducible selections for every transversal, we derive a polynomial-time algorithm for ACS+A$\cdot$Enum whenever the conclusion-degree of $x$ is bounded by a constant.

$◀$

We conclude to the following, as a corollary of Theorems 6 and 8, and proving the case of bounded-conclusion degree in Theorem 1.

Let us remark that in our algorithm, we actually do not need the knowledge of $\mathrm{irr}(a)$ for all ancestors of $x$, but only for those in a premise which has $x$ in conclusion. This however makes no asymptotic difference on the final complexity we get for ICS$\cdot$Enum.

Also, it appears in the proof of Theorem 8 that we only need a constant upper bound on the size $k$ of a minimal transversal of ${\mathscr{H}}_x$, to derive an input-polynomial time algorithm solving ACS+A$\cdot$Enum. We immediately derive the following generalization of Theorem 9 dealing with hypergraphs of bounded dual-dimension (admitting minimal transversals of bounded size) who define complements of conformal hypergraphs [6].

We end the section by showing the limitations of this approach in order to get output-polynomial time bounds whenever we drop the condition of bounded conclusion-degree.

First, note that the key step of the approach is to compute all possible intersections as provided in Lemma 7. However, there are cases where the number of possible such intersections is exponential in $|\mathrm{irr}(\mathrm{\Sigma })|$, which typically occurs if minimal transversals of ${\mathscr{H}}_x$ are of unbounded size, or if $\mathrm{MHS}({\mathscr{H}}_x)$ is of exponential size in $\mathrm{irr}(x)$.

To get one such example, consider $k\in \mathbb{N}$ and the implicational base defined by $X=\{a_1,b_1,\mathrm{\dots },a_k,b_k,x\}$ and ; see Figure 3 for an illustration. Then $\mathrm{irr}(x)=\{{(a_i)}_{1\le i\le j}\cup {(b_i)}_{j+1\le i\le k}:0\le j\le k\}$ so $|\mathrm{irr}(x)|=k+1$, and the other elements in $X\setminus \{x\}$ are easily seen to have a single attached closed set. Therefore, $\mathrm{irr}(\mathrm{\Sigma })$ is of polynomial size in $|X|=2k+1$ and $|\mathrm{\Sigma }|=2k-1$. However, $|\mathrm{MHS}({\mathscr{H}}_x)|=2^k$ and computing this set would fail in providing an output-polynomial time algorithm for enumerating $\mathrm{irr}(x)$.

At last, we note that this example has bounded premise-degree. We will show however in the next section that such instances can actually be efficiently solved by solution graph traversal.

We provide an incremental-polynomial time algorithm solving ICS$\cdot$Enum whenever the given implicational base has bounded premise-degree. Our algorithm relies on the top-down approach from Section 3 and solves ACS+A$\cdot$Enum relying on the solution graph traversal technique.

In the solution graph traversal framework, one has to define a digraph called solution graph, whose nodes are the solutions we aim to enumerate, and whose arcs $(F,F^{\prime })$ consists of ways of reconfigurating a given solution $F$ into another solution $F^{\prime }$. Then, the goal is not to build the solution graph entirely, but rather to traverse all its nodes efficiently and avoiding repetitions of nodes. This general technique has been fruitfully applied to numerous enumeration problems, see e.g., [9, 27, 40], and generalized to powerful frameworks [2, 10, 11]. In the following we will use the next folklore result which states conditions for such a technique to be efficient; see [20] for a quantitative statement and a proof.

In the following, let us consider an instance of ACS+A$\cdot$Enum, i.e., we fix some acyclic implicational base $(X,\mathrm{\Sigma })$, an element $x\in X$, and we assume that we are given $\mathrm{irr}(y)$ for all ancestors $y$ of $x$.

We first argue that Condition 1 holds for ACS+A$\cdot$Enum. Let ${\mathrm{GC}}_x$ be a function which maps any $E\subseteq X$ such that $x\notin \varphi (E)$ to a maximal set $M\supseteq E$ with this property. We call the resulting set the greedy completion of $E$. Note that ${\mathrm{GC}}_x(E)$ can be computed in polynomial time in the size of $(X,\mathrm{\Sigma })$, and that the obtained set lies in $\mathrm{irr}(x)$; see Section 2. We derive the following.

We now turn on showing the existence of a polynomial-time computable neighboring function satisfying Conditions 2 and 3. Given some irreducible closed set $M\in \mathrm{irr}(x)$, and some element $y\in X\setminus M$, we define

In other words, ${\mathscr{H}}_{M,y}$ is the hypergraph of premises of $\mathrm{\Sigma }$ not included in $M$, triggered by adding $y$, and with a conclusion not in $M$. Note that $|{ℰ}_{M,y}|\le \mathrm{pdeg}(y)\le \mathrm{pdeg}(\mathrm{\Sigma })$. Also, because every premise in ${ℰ}_{M,y}$ implies a $b\notin M$, hence an ancestor of $x$, we derive the following observation by transitivity.

Regarding Condition 2, we first need the following statement, which holds the same idea as Lemma 7.

$◀$

We are now ready to define the aforementioned neighboring function. Given $M\in \mathrm{irr}(x)$ and $y\notin M$, we define

and put $𝒩(M):={\bigcup }_{y\notin M}𝒩(M,y)$. We prove that Conditions 2 and 3 hold for this function.

$◀$

Note that Condition 2 is ensured by Observation 15 and Lemma 16. We are thus left to prove Condition 3, which we obtain by proving that for any pair of solutions, there is a neighbor of the first one with greater intersection with the second.

$◀$

Combining Theorem 11, Lemma 12, Lemma 16, and Corollary 18, we obtain a polynomial-delay algorithm for ACS+A$\cdot$Enum by solution graph traversal for acyclic implicational bases of bounded premise-degree. This, together with Theorem 6, in turn implies the following theorem, proving the remaining case of bounded premise-degree in Theorem 1.

As in the previous section, we only needed to bound the size of a minimal transversal of ${\mathscr{H}}_{M,y}$ in the proof of previous theorem to derive an input-polynomial time algorithm solving ACS+A$\cdot$Enum. This gives the following result, analogous to Theorem 10.

In this paper, we described two incremental-polynomial time algorithms for the enumeration of irreducible closed sets in acyclic convex geometries of bounded (premise- or conclusion-) degree. This solves one of the two translation task for this class, the other one being addressed in the long version of this work [16]. We note that the delay of our algorithms is intrinsically not polynomial since our algorithm rely on a sequential top-down procedure which reduces the enumeration to an auxiliary enumeration problem whose instance grows with the total number of solutions output so far. This suggests the following question.

Toward this direction, we now argue that the classic flashlight search framework may not be used in a straightforward way to obtain a positive answer to this question. In the flashlight search technique, the goal is to construct solutions one element at a time, according to a linear order $x_1,\mathrm{\dots },x_n$ on the ground set, and deciding at each step whether $x_i$ should or should not be included in the solution. For this approach to be tractable, the framework requires to solve the so-called “extension problem” in polynomial time: given two disjoint subsets $K,F$ of the ground set, decide whether there exists a solution including $K$ and avoiding $F$. We refer to, e.g., [9, 30] for a more detailed description of this folklore technique. More formally, this technique reduces the enumeration to the following decision problem.

We show that this problem is NP-complete even for acyclic implicational bases of bounded degree with $K=\mathrm{\varnothing }$, suggesting that this framework may not be used in a straightforward way to improve our results. Let us however remark that this does not rule out the possibility of a polynomial-delay algorithm for the problem, using a different approach or relying on particular vertex orderings. We refer to [16] for the proof of this result, the construction of which is hinted in Figure 4.

Note that, as an intermediate step, one may wonder whether there exists an incremental-polynomial time algorithm for ICS$\cdot$Enum where the degree of the polynomial in the number of solutions is independent of the premise degree.

Among other directions, it is natural to ask whether our results extend to broader classes of closure systems or to parameters that generalize the degree. We include a thorough discussion on the relevant classes and parameters in the long version of this work [16] as well as some considerations related to parameterized enumeration. In particular, we argue that without acyclicity the degree alone is not helpful anymore as ICS$\cdot$Enum for instances with bounded degree becomes as general as ICS$\cdot$Enum.