Constant Amortized Time Enumeration of Independent Sets for Graphs with Forbidden Subgraphs on Fixed Number of Vertices
share
In this paper, we address the independent set enumeration problem. Although many efficient enumeration algorithms for maximal independent sets have been proposed, no fine-grained analysis for the non-maximal variant has not been given. As the main result, we propose an algorithm EIS for the non-maximal variant that runs in amortized O(q) time and liner space, where q is the maximum integer such that there is no clique with q vertices in the given graph. Note that EIS correctly works even if we do not know the exact value of q. In addition, it is known that several sparse graph class have constant clique number which is defined by the size of a maximum clique, e.g., triangle-free graphs, planer graphs, bounded degenerate graphs, locally bounded expansion graphs, and so on. Hence, as a by product, EIS is optimal when input graphs are in a graph class with forbidden subgraphs on fixed number of vertices.
READ FULL TEXT