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.
$\begingroup$
$\endgroup$
7
-
$\begingroup$ 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. $\endgroup$– LaakeriJan 6, 2020 at 11:45
-
$\begingroup$ @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. $\endgroup$– Kristina DedndreajJan 6, 2020 at 12:06
-
1$\begingroup$ 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. $\endgroup$– JuhoJan 6, 2020 at 12:52
-
$\begingroup$ @Juho: The picture in this link explains what it means to generate here. Hopefully it is clear enough. $\endgroup$– Kristina DedndreajJan 6, 2020 at 16:42
-
$\begingroup$ 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. $\endgroup$– JuhoJan 6, 2020 at 16:50
|
Show 2 more comments
1 Answer
$\begingroup$
$\endgroup$
5
This does not seem likely to be useful in any application. We already know of straightforward algorithms for constructing all vertex subsets, and they are are about as efficient as possible. So, if you have a complicated way to construct all vertex subsets, that's not particularly useful, as it is a more complicated way to do something we already know how to do in a simpler way. I cannot imagine any reason why an application would choose your method instead of standard methods.
-
$\begingroup$ I have found a lot of literature regarding construction of the set of spanning subgraphs of a graph using the set of its spanning trees by making use of the activities as defined by Tutte. This approach is not considered straightforward though since one needs to know first the set of the spanning trees. I would like to read more about similar approaches regarding the vertex subsets but I have not succeeded in finding literature so far. I am not concerned with just a complete enumeration of the vertex subsets, I want something which provides some structural insight for the graph in play. $\endgroup$ Jan 7, 2020 at 9:36
-
$\begingroup$ @KristinaDedndreaj, I don't expect there to be any literature about how to generate all subsets of the vertices, as that is so trivial to do that it is not research-worthy and (I am guessing) would not appear in a research paper. $\endgroup$– D.W. ♦Jan 7, 2020 at 9:39
-
$\begingroup$ I think I am failing to deliver properly what I want to say but I do not agree that constructing all vertex subsets with requirements on beneficial structural meaning is trivial since its edge counterpart is far away from it. On some scenarios, one could, for example, reduce the analysis of all vertex subsets to only a couple of them. The edge set is even blessed with a matroid structure whose independent sets are its set of spanning trees, this is not true for the vertex set however because the set of vertex independent subsets does not satisfy the augmentation property. $\endgroup$ Jan 7, 2020 at 10:04
-
$\begingroup$ @KristinaDedndreaj, Perhaps I haven't understood what you have in mind. I don't know what "requirements on beneficial structural meaning" means, and I don't see that stated in the question. Perhaps you'd like to ask a new question describing more clearly the exact problem that you're thinking of, and ask for the best algorithm for that problem? $\endgroup$– D.W. ♦Jan 7, 2020 at 17:47
-
$\begingroup$ English is not my native language so that could be one of the reasons I cannot state the problem in an optimal way. I will try to reformulate it once I get the chance. $\endgroup$ Jan 8, 2020 at 14:35