Algorithms with improved delay for enumerating connected induced subgraphs of a large cardinality

Abstract

The problem of enumerating all connected induced subgraphs of a given order $k$ from a given graph arises in many practical applications: bioinformatics, information retrieval, processor design,to name a few. The upper bound on the number of connected induced subgraphs of order $k$ is $n\cdot \frac{(e\hat{I}”{)}^k}{(\hat{I}”-1)k}$, where $\hat{I}”$ is the maximum degree in the input graph $G$ and $n$ is the number of vertices in $G$. In this short communication, we first introduce a new neighborhood operator that is the key to design reverse search algorithms for enumerating all connected induced subgraphs of order $k$. Based on the proposed neighborhood operator, three algorithms with delay of $O(k\cdot min\{(n-k),k\hat{I}”\}\cdot (k\log \hat{I}”+\log n))$, $O(k\cdot min\{(n-k),k\hat{I}”\}\cdot n)$ and $O(k^2\cdot min\{(n-k),k\hat{I}”\}\cdot min\{k,\hat{I}”\})$ respectively are proposed. The first two algorithms require exponential space to improve upon the current best delay bound $O(k^2\hat{I}”)$\cite{4} for this problem in the case $k>\frac{n\log \hat{I}”-\log n-\hat{I}”+\sqrt{n\log n\log \hat{I}”}}{\log \hat{I}”}$ and $k>\frac{n^2}{n+\hat{I}”}$ respectively.