Design of Polynomial-delay Enumeration Algorithms in Transitive Systems

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

In this paper, as a new notion, we define a transitive system to be a set system (V, š’žāŠ† 2^V) on a finite set V of elements such that every three sets X,Y,Zāˆˆš’ž with ZāŠ† Xāˆ© Y implies XāˆŖ Yāˆˆš’ž, 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 in delay bounded by a polynomial with respect to the input size and the running times of the oracles. The proposed algorithm yields the first polynomial-delay algorithms for enumerating connectors in an attributed graph and for enumerating all subgraphs with various types of connectivities such as all k-edge/vertex-connected induced subgraphs and all k-edge/vertex-connected spanning subgraphs in a given undirected/directed graph for a fixed k.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset