Compression with wildcards: Enumerating specific induced subgraphs, and packing them as well

Abstract

Various algorithms have been proposed to enumerate all connected induced subgraphs of a graph $G=(V,E)$. As a variation we enumerate all "packings of connected sets", i.e. partitions $\hat{I}$ of $V$ with the property that each part of $\hat{I}$ induces a connected subgraph. More generally, for various types $T$ of graphs we do (one or both of) the following: (i) enumerate all type $T$ (induced) subgraphs of a given graph $G$, or (ii) enumerate all packings of type $T$ subgraphs of $G$

24 pages, 8 figures