Compression with wildcards: All induced metric subgraphs

Driven by applications in the natural, social and computer sciences several algorithms have been proposed to enumerate all sets $X\text{s}V$ of vertices of a graph $G=(V,E)$ that induce a {\it connected} subgraph. We offer two algorithms for enumerating all $X$’s that induce (more exquisite) {\it metric} subgraphs. Specifically, the first algorithm, called {\tt AllMetricSets}, generates these $X$’s in a compressed format. The second algorithm generates all (accessible) metric sets one-by-one but is provably output-polynomial. Mutatis mutandis the same holds for the geodesically-convex sets $X\text{s}V$, this being a natural strengthening of “metric”. The Mathematica command {\tt BooleanConvert} features prominently.