Polynomial-delay Enumeration Algorithms in Set Systems
We consider a set system (V, šā 2^V) on a finite set V of elements, where we call a set Cāš a component. We assume that two oracles L_1 and L_2 are available, where given two subsets X,Yā V, L_1 returns a maximal component Cāš with Xā Cā Y; and given a set Yā V, L_2 returns all maximal components Cāš with Cā Y. Given a set I of attributes and a function Ļ:Vā 2^I in a transitive system, a component Cāš is called a solution if the set of common attributes in C is inclusively maximal; i.e., ā_vā CĻ(v)āā_vā XĻ(v) for any component Xāš 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.
READ FULL TEXT