# Maximal Closed Set and Half-Space Separations in Finite Closure Systems

arXiv: https://arxiv.org/abs/2001.04417 · HTML: https://mlsanity.com/paper/2001.04417/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Jan 2020.

## Built on by (most cited first, 5 of 5)

- [Exact Recovery of Clusters in Finite Metric Spaces Using Oracle Queries](https://mlsanity.com/paper/2102.00504/) (2021)
- [Efficient Algorithms for Learning Monophonic Halfspaces in Graphs](https://mlsanity.com/paper/2405.00853/) (2024)
- [Learning Weakly Convex Sets in Metric Spaces](https://mlsanity.com/paper/2105.06251/) (2021)
- [Efficient Algorithms for Learning and Compressing Monophonic Halfspaces in Graphs](https://mlsanity.com/paper/2506.23186/) (2025)
- [Self-Directed Learning of Convex Labelings on Graphs](https://mlsanity.com/paper/2409.01428/) (2024)

## Abstract (arXiv)

Several concept learning problems can be regarded as special cases of half-space separation in abstract closure systems over finite ground sets. For the typical scenario that the closure system is implicitly given via a closure operator, we show that the half-space separation problem is NP-complete. As a first approach to overcome this negative result, we relax the problem to maximal closed set separation, give a generic greedy algorithm solving this problem with a linear number of closure operator calls, and show that this bound is sharp. For a second direction, we consider Kakutani closure systems and prove that they are algorithmically characterized by the greedy algorithm. As a first special case of the general problem setting, we consider Kakutani closure systems over graphs and give a sufficient condition for this kind of closure systems in terms of forbidden graph minors. For a second special case, we then focus on closure systems over finite lattices, give an improved adaptation of the generic greedy algorithm, and present an application concerning subsumption lattices.