Polynomial-delay Enumeration Algorithms in Set Systems

Abstract

We consider a set system $(V,\mathcal{C}\subseteq 2^V)$ on a finite set $V$ of elements, where we call a set $C\in \mathcal{C}$ a component. We assume that two oracles ${\mathrm{L}}_1$ and ${\mathrm{L}}_2$ are available, where given two subsets $X,Y\subseteq V$, ${\mathrm{L}}_1$ returns a maximal component $C\in \mathcal{C}$ with $X\subseteq C\subseteq Y$; and given a set $Y\subseteq V$, ${\mathrm{L}}_2$ returns all maximal components $C\in \mathcal{C}$ with $C\subseteq Y$. Given a set $I$ of attributes and a function $\sigma :V\to 2^I$ in a transitive system, a component $C\in \mathcal{C}$ is called a solution if the set of common attributes in $C$ is inclusively maximal; i.e., ${\bigcap }_{v\in C}\sigma (v)⊋{\bigcap }_{v\in X}\sigma (v)$ for any component $X\in \mathcal{C}$ with $C⊊X$. We prove that there exists an algorithm of enumerating all solutions (or all components) in delay bounded by a polynomial with respect to the input size and the running times of the oracles.

arXiv admin note: substantial text overlap with arXiv:2004.01904

References in corpus (1)

• Design of Polynomial-delay Enumeration Algorithms in Transitive Systems