# How do I get a different (random) independent edge set each time I run FindIndependentEdgeSet?

I'd like to use FindIndependentEdgeSet[g] repeatedly to get random maximal matchings of a fixed graph, but each time I call this function it gives me the same answer (i.e. the same list of edges).

How do I "randomise" it?

-
@Öskå Select[Subsets[EdgeList[g = CycleGraph[4]]], IndependentEdgeSetQ[g, #] && Length@# == 2 &] – Dr. belisarius May 23 '14 at 0:00
@belisarius R-r-r-ight :) Deleting comments so I don't look stupid :P – Öskå May 23 '14 at 9:08

Example graph:

g = PetersenGraph[5, 5];


Get independent edge sets:

indies = Select[Subsets[EdgeList[g]], IndependentEdgeSetQ[g, #] &];


Get some random set (repeat as needed):

RandomChoice[indies]


(* {1<->1, 2<->2, 3<->3, 4<->9, 6<->7} *)

Edit: Rahul notes I missed the "maximal" part.

(* pull out only longest sets *)
With[{ml = Max[Length /@ indies]}, indiesM = Select[indies, Length[#] == ml &]];

(* repeat as needed *)
RandomChoice[indiesM]

-
This does not always give maximal matchings. So it solves the problem in the title of the question but not the one in the body... – Rahul May 23 '14 at 4:16
@RahulNarain: Thanks for catching, edited. – ciao May 23 '14 at 6:29