# Literature request: Generating all vertex subsets of a graph

I am working in an algorithm which finds a unique maximal independent set of vertices. Then, using this set, one can construct all other vertex subsets. I assume this might have some applications outside mathematics, especially in computer science, but I am not sure where I can read about such applications. Does anyone have any good literature suggestion which describes scenarios where this could be useful? The idea is somehow similar to that of using edge activities as defined by Tutte in order to construct all possible subgraphs of a given graph by using the set of its trees.

• Can you explain more what it means to "generate all other vertex subsets"? Enumerating all maximal independent set is a well researched problem, and has polynomial delay algorithms. Jan 6 '20 at 11:45
• @Laakeri: What I mean is that given a graph $G=(V,E)$ we can find a unique vertex maximal independent set $S\in \mathscr{P}(V)$ which generates $\mathscr{P}(V)$. So I am concerned about generating all vertex subsets not just vertex maximal independent sets. Jan 6 '20 at 12:06
• What does it mean "to generate" here? If you want to list all vertex subsets, there's essentially no algorithm faster than the one that steps through the power set of the list of vertices.
– Juho
Jan 6 '20 at 12:52
• @Juho: The picture in this link explains what it means to generate here. Hopefully it is clear enough. Jan 6 '20 at 16:42
• I suggest adding all relevant information to the question to make it self-contained. Comments do disappear over time and hyperlinks tend to die as well.
– Juho
Jan 6 '20 at 16:50