2
$\begingroup$

I am finding independent sets of a graph. These independent sets should include certain specified vertices of the graph.

If there is only one specified vertex, we can do:

FindIndependentVertexSet[{g,v},…]

I can change v for the element I want. The thing is, I want to extract independent sets which include multiple vertices.

Is it possible? Is there any way to do it?

$\endgroup$
  • $\begingroup$ You could delete all the neighbours of the chosen vertices and then find an independent set of the new graph...? $\endgroup$ – Rahul Jan 3 '17 at 22:33
  • $\begingroup$ I did that, and it works, but I prefer a simpler solution. $\endgroup$ – forumcash Jan 9 '17 at 4:24
1
$\begingroup$

I don't know if FindIndependentSet can be used directly if you are forcing two or more vertices to be part of a solution.

In the following, I'm making use of an earlier answer to generate subsets with specific properties:

g = RandomGraph[{8, 14}, VertexLabels -> "Name"];

ClearAll[subsetsF];
subsetsF[list_, members_, size_: All, number_: All] := 
 With[{list2 = (list /. Thread[members -> Sequence[]])}, 
  Join[#, members] & /@ Subsets[list2, size, number]]

(* These vertices are forced to be part of a solution *)
forced = {1, 2};
candidates = Reverse[subsetsF[VertexList[g], forced]];

SelectFirst[candidates, IndependentVertexSetQ[g, #] &]
HighlightGraph[g, %]

Essentially, what the above does is that it generates all subsets of the vertex set containing our specific vertices. Then, it simply picks the first (largest) one that induces an independent set in the graph. This is the straightforward brute-force method, but I'll give you another possibility.

Assuming FindIndependentSet can only start with one forced vertex, we could also generate all possible solutions, and prune away the ones that don't satisfy our constraints:

g = RandomGraph[{8, 14}, VertexLabels -> "Name"];

forced = {1, 2};
inds = FindIndependentVertexSet[{g, First[forced]}, Infinity, All];

(* All possible solutions *)
Select[inds, SubsetQ[#, forced] &]

Furthermore, assuming that forced indeed holds more than just a single vertex, I suggest the following heuristic to speed up computation. Instead of an arbitrary vertex, choose as a "starting vertex" the one with the highest degree: intuitively, if a vertex of large degree is included in your solution, it prunes away all of its neighbors, thus hopefully giving us some speed. With this heuristic, the above can be rewritten to:

g = RandomGraph[{8, 14}, VertexLabels -> "Name"];

forced = {1, 2};
p = TakeLargestBy[forced, VertexDegree[g, #] &, 1];
inds = FindIndependentVertexSet[{g, p}, Infinity, All];

(* All possible solutions *)
Select[inds, SubsetQ[#, forced] &]
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.