Arnaud Mary ; Yann Strozecki - Efficient enumeration of solutions produced by closure operations

dmtcs:4143 - Discrete Mathematics & Theoretical Computer Science, June 13, 2019, Vol. 21 no. 3 -
Efficient enumeration of solutions produced by closure operationsArticle

Authors: Arnaud Mary ORCID; Yann Strozecki

    In this paper we address the problem of generating all elements obtained by the saturation of an initial set by some operations. More precisely, we prove that we can generate the closure of a boolean relation (a set of boolean vectors) by polymorphisms with a polynomial delay. Therefore we can compute with polynomial delay the closure of a family of sets by any set of "set operations": union, intersection, symmetric difference, subsets, supersets $\dots$). To do so, we study the $Membership_{\mathcal{F}}$ problem: for a set of operations $\mathcal{F}$, decide whether an element belongs to the closure by $\mathcal{F}$ of a family of elements. In the boolean case, we prove that $Membership_{\mathcal{F}}$ is in P for any set of boolean operations $\mathcal{F}$. When the input vectors are over a domain larger than two elements, we prove that the generic enumeration method fails, since $Membership_{\mathcal{F}}$ is NP-hard for some $\mathcal{F}$. We also study the problem of generating minimal or maximal elements of closures and prove that some of them are related to well known enumeration problems such as the enumeration of the circuits of a matroid or the enumeration of maximal independent sets of a hypergraph. This article improves on previous works of the same authors.

    Volume: Vol. 21 no. 3
    Section: Discrete Algorithms
    Published on: June 13, 2019
    Accepted on: June 4, 2019
    Submitted on: December 12, 2017
    Keywords: Computer Science - Computational Complexity,Computer Science - Discrete Mathematics,Computer Science - Data Structures and Algorithms
      Source : OpenAIRE Graph
    • Aggregation Queries; Funder: French National Research Agency (ANR); Code: ANR-14-CE25-0017

    1 Document citing this article

    Consultation statistics

    This page has been seen 913 times.
    This article's PDF has been downloaded 433 times.