Polynomial-delay Enumeration Algorithms in Set Systems

04/16/2020
āˆ™
by   Kazuya Haraguchi, et al.
āˆ™
0
āˆ™

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

Please sign up or login with your details

Forgot password? Click here to reset