A Linear Delay Algorithm for Enumeration of 2-Edge/Vertex-connected Induced Subgraphs

For a set system $(V,\mathcal{C}\subseteq 2^V)$, we call a subset $C\in \mathcal{C}$ a component. A nonempty subset $Y\subseteq C$ is a minimal removable set (MRS) of $C$ if $C\setminus Y\in \mathcal{C}$ and no proper nonempty subset $Z⊊Y$ satisfies $C\setminus Z\in \mathcal{C}$. In this paper, we consider the problem of enumerating all components in a set system such that, for every two components $C,C^{\mathrm{\prime }}\in \mathcal{C}$ with $C^{\mathrm{\prime }}⊊C$, every MRS $X$ of $C$ satisfies either $X\subseteq C^{\mathrm{\prime }}$ or $X\cap C^{\mathrm{\prime }}=\mathrm{\varnothing }$. We provide a partition-based algorithm for this problem, which yields the first linear delay algorithms to enumerate all 2-edge-connected induced subgraphs, and to enumerate all 2-vertex-connected induced subgraphs.