Characterizing the optimum bases of a convex geometry using quasi-closed hypergraphs
This work addresses the optimization of implicational bases in convex geometries, providing a unified framework for tractable cases, but it is incremental as it builds on prior hardness results and specific class analyses.
The paper characterizes optimum implicational bases for convex geometries using quasi-closed hypergraphs, showing that polynomial-time optimization is possible when these hypergraphs have disjoint edges, and applies this to several known classes like double-shelling and affine convex geometries.
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.