Polynomial-delay Enumeration Algorithms in Set Systems

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$;andgivenaset$Y\subseteq V$,$$\mathrm{L}$_2$returnsallmaximalcomponents$C\in {\mathcal C}$with$C\subseteq Y$\mathrm{.}Givenaset$I$ofattributesandafunction$\sigma:V\to 2^I$inatransitivesystem,acomponent$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.