Characterizing the optimum bases of a convex geometry using quasi-closed hypergraphs
Anthony Meunier, Lhouari Nourine, Simon Vilmin · 2026
Read Characterizing the optimum bases of a convex geometry using quasi-closed hypergraphs by Anthony Meunier, Lhouari Nourine, Simon Vilmin (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-14615.txt.
Introduction
Meunier, Nourine and Vilmin characterize optimum implicational bases of convex geometries via new hypergraphs. Shrinking the premises and conclusions of a base is hard in general. Their quasi-closed hypergraphs capture what optimum bases look like. When the edges of each such hypergraph stay disjoint, known algorithms optimize any base in polynomial time. The condition covers double-shelling, acyclic, affine and acceptant geometries. Old tractability results for the first three classes fall under one roof.
Catalog record
| CREATOR | Anthony Meunier, Lhouari Nourine, Simon Vilmin |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 58816 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.14615
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Characterizing the optimum bases of a convex geometry using quasi-closed hypergraphs Anthony Meunier, Lhouari Nourine, Simon Vilmin Abstract Optimizing an implicational base of a closure system consists in turning this implicational base into an equivalent one with premises and conclusions as small as possible. This task is known to be hard in general but tractable for a number of classes of closure systems. In particular, several classes of convex geometries are known to have tractable optimization, while the problem was recently claimed to remain hard in general convex geometries. Continuing this line of research, we give a characterization of the optimum bases of a convex geometry in terms of what we call quasi-closed hypergraphs. We then use this characterization to show that when each quasi-closed hypergraph has disjoint edges, any implicational base of the convex geometry can be optimized in polynomial time with existing minimization and reduction algorithms. Finally, we prove that this property applies to double-shelling, acyclic, affine and acceptant convex geometries, thus unifying the existing results regarding the tractability of optimization for the first three classes. Keywords: closure systems, implicational bases, optimum bases, convex geometries. 1 Introduction Implications, also known as attribute implications in Formal Concept Analysis [ 20 ] , functional dependencies in database theory [ 30 , 31 ] , Horn clauses in logic [ 11 , 23 ] , or join-covers in lattice theory [ 10 ] to cite a few, are a common representation of finite closure systems. Indeed, a closure system can always be represented by several (equivalent) implicational bases—i.e., collections of implications. Within the study of implicational bases, the task of turning an implicational base into a smaller one has been the topic of numerous research. Several measures of the size of an implicational base have been defined and studied: the number of implications, the sum of sizes of the premises of its implications, of the conclusions, or both. An implicational base that minimizes the number of implications is minimum . It is left-optimum (resp. right-optimum ) if the sum of sizes of its premises (resp. conclusions) is as small as possible. It is optimum if the sum of the sizes of all its premises and conclusions is minimum among all other equivalent bases. We refer to Section 2 for formal definitions. In this paper we are interested in the optimization problem: given an implicational base of a closure system, find, or turn the implicational base into, an equivalent optimum implicational base. This problem has been studied from different perspectives such as database theory [ 29 , 4 , 29 ] , propositional logic [ 22 , 23 , 11 , 12 , 19 , 27 ] , or closure systems and lattices [ 36 , 37 , 34 , 1 , 2 , 8 ] . We review below the main results on optimization and redirect the reader to [ 15 , section 6.7] and [ 38 , 19 ] for further references on the topic. The first result is due to Maier [ 29 ] in his work on covers of functional dependencies. In that paper, he proves that the decision problem associated to optimization is \mathsf{NP} -complete for arbitrary closure systems and that optimum bases must be minimum. Mannila and Raïha [ 32 ] then investigate further optimum bases and prove that an optimum implicational base must be left-optimum and that an implicational base is optimum if and only if each of its equivalence class is optimum. The equivalence classes of an implicational base are the sets of implications whose premises share the same closure. This latter result was recently reproved for right-optimization by Bichoupan [ 8 , unpublished] , answering an open question of Adaricheva and Nation [ 1 ] , albeit with a different phrasing: the (right-)size of an equivalence class in any optimum implicational base is fixed. Ausiello et al. [ 4 ] (see also [ 5 ] ), prove that both left- and right-optimization are \mathsf{NP} -complete, which gives a new proof of the hardness of the optimization task. They also complete the connection between the different minimality measures: an optimum base is both left- and right-optimum. It thus follows that an implicational base is optimum if and only if it is both left- and right-optimum (see also [ 1 ] ). In the language of closure systems and implicational bases, Wild [ 36 , 37 ] shows that both modular closure systems and simple binary matroids can be optimized in polynomial time. More precisely, for simple binary matroids, he shows that the corresponding closure system does have a unique optimum base that can be found in polynomial time, a result recently rediscovered by Berczi et al. [ 6 ] . In [ 22 ] , Hammer and Kogan give a new proof that optimization is \mathsf{NP} -complete, this time in the language of Horn CNFs. Later [ 23 ] , they proved that optimization could be achieved in polynomial time for acyclic and quasi-acyclic Horn functions. In particular, they prove that each acyclic Horn function also has a unique optimum implicational base. In [ 11 ] Boros et al. generalize the results of Hammer and Kogan and show that optimization is tractable for the more general classes of component quadratic Horn functions based on earlier results regarding essential and exclusive sets of implicates [ 12 ] they used to give new proofs that quadratic, quasi-acyclic and acyclic Horn functions can be optimized. Then, in another contribution [ 19 ] , Boros et al. proved that optimization remains hard even for implicational bases with premises of size 2 . This result was later strengthened by Kučera [ 27 ] , who proves that optimization remains hard even in implicational bases where all premises have size 2 and the same closure, the ground set. Besides, in the language of closure systems, Adaricheva and Nation [ 1 ] proved that optimization and right-optimization remain hard even within the class of bounded closure systems. Convex geometries are yet another classes of closure systems that has recently received attention regarding optimization [ 34 , 2 , 8 ] . Convex geometries [ 18 ] , closure systems with anti-exchange closure operator, have been studied and rediscovered in many fields ranging from combinatorial optimization to social choice theory (see [ 33 , 26 ] ). For optimization, Kashiwabara and Nakamura [ 34 ] proved that affine convex geometries, that is convex geometries arising from point configurations in \mathbb{R}^{d} can be optimized in polynomial time. This result, as well as the result of Hammer and Kogan [ 23 ] on acyclic Horn functions, also known as acyclic convex geometries, poset-type convex geometries or G -geometries (see, e.g., [ 23 , 36 , 2 , 16 ] ), has then been generalized by Adaricheva [ 2 ] . In that contribution, the author prove that convex geometries with the Carousel property, D -geometries and double-shelling convex geometries do have tractable optimization. Convex geometries with the Carousel property generalize affine convex geometries. D -geometries are precisely the intersection of lower-bounded and lower-semimodular closure systems, and properly contain acyclic convex geometries. Double-shelling convex geometries, also well-studied (see, e.g., [ 18 , 2 , 24