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

Abstract

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^{\prime }\in \mathcal{C}$ with $C^{\prime }⊊C$, every MRS $X$ of $C$ satisfies either $X\subseteq C^{\prime }$ or $X\cap C^{\prime }=\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.

The preliminary version of the paper has been submitted to IWOCA 2023