Comparison of Algorithms and Implementations for Enumerating Support-closed Connected Induced Subgraphs
Daiki Watanabe, Takumi Tada, Kazuya Haraguchi · Journal of Information Processing · 2024
Suppose that we are given a tuple (G, I, σ) of an undirected graph G=(V, E), an itemset I={1, 2, ..., q}, and a mapping σ:V → 2I. For S ⊆ V, let us denote Iσ(S):=⋂v∈Sσ(v). We say that S induces a support-closed connected subgraph if S is maximal with respect to the connectivity and the common itemset (i.e., the subgraph G[S] induced by S is connected and, for any v ∈ V \ S, G[S ∪ {v}] is disconnected or Iσ(S ∪ {v})⊊ Iσ(S)). Several algorithms have been developed for enumerating all support-closed connected induced subgraphs, where some of them are shown to be polynomial-amortized or polynomial-delay. However, a theoretical complexity bound does not necessarily represent the empirical performance of an algorithm. In this paper, we compare the empirical performance of four enumeration algorithms named COPINE (branch-and-bound), COOMA (dynamic programming), FT (family-tree) and BP (binary partition), respectively. We observe that, for random instances, COOMA is generally the fastest, followed by BP, and that these two algorithms are more robust to parameters of random instances than the other two. We then extend BP to a problem that arises from bacterial GWAS (Genome-Wide Association Studies) and observe that its implementation is much faster than an existing implementation of CALDERA, a previous algorithm.