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

  • 2020-01-13 17:34:47
  • Florian Seiffarth, Tamas Horvath, Stefan Wrobel
  • 2


We investigate some algorithmic properties of closed set and half-spaceseparation in abstract closure systems. Assuming that the underlying closuresystem is finite and given by the corresponding closure operator, we show thatthe half-space separation problem is NP-complete. In contrast, for the relaxedproblem of maximal closed set separation we give a greedy algorithm usinglinear number of queries (i.e., closure operator calls) and show that thisbound is sharp. For a second direction to overcome the negative result above,we consider Kakutani closure systems and prove that they are algorithmicallycharacterized by the greedy algorithm. As one of the major potentialapplication fields, we then focus on Kakutani closure systems over graphs andgeneralize a fundamental characterization result based on the Pasch axiom tograph structured partitioning of finite sets. In addition, we give a sufficientcondition for Kakutani closure systems over graphs in terms of graph minors.For a second application field, we consider closure systems over finitelattices, present an adaptation of the generic greedy algorithm to this kind ofclosure systems, and consider two potential applications. We show that for thespecial case of subset lattices over finite ground sets, e.g., for formalconcept lattices, its query complexity is only logarithmic in the size of thelattice. The second application is concerned with finite subsumption latticesin inductive logic programming. We show that our method for separating two setsof first-order clauses from each other extends the traditional approach basedon least general generalizations of first-order clauses. Though our primaryfocus is on the generality of the results obtained, we experimentallydemonstrate the practical usefulness of the greedy algorithm on binaryclassification problems in Kakutani and non-Kakutani closure systems.


Quick Read (beta)

loading the full paper ...