Design of Polynomial-delay Enumeration Algorithms in Transitive Systems
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