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,\mathcal{C}\subseteq 2^V)$ on a finite set $V$ of elements such that every three sets $X,Y,Z\in \mathcal{C}$ with $Z\subseteq X\cap Y$ implies $X\cup Y\in \mathcal{C}$, 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$; and given a set $Y\subseteq V$, ${\mathrm{L}}_2$ returns all maximal components $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 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$.