IndependetVertexSetQ Bug
- To: mathgroup at smc.vnet.net
- Subject: [mg117898] IndependetVertexSetQ Bug
- From: Eduardo F <eduardofeo at gmail.com>
- Date: Sat, 2 Apr 2011 17:06:31 -0500 (EST)
Hello
I have found what seems to be a bug inside the implementation of
IndependetVertexSetQ predicate. I realized it after using this
predicate inside my code thousands of times, which caused the computer
to run out of memory.
Using an alternative definition, and comparing the time it takes to
compute, it is clear that something is not right inside the provided
implementation. I'm using Mathematica 8.0.
G = RandomGraph[{16, 20}];
S = Cases[Subsets[VertexList[G]], Except[{}]];
MyIndependentVertexSetQ[g_, s_] :=
Length[EdgeList[Subgraph[g, s]]] == 0;
Timing[T1 = Table[IndependentVertexSetQ[G, s], {s, S}];]
{19.81000000000001`, Null}
Timing[T2 = Table[MyIndependentVertexSetQ[G, s], {s, S}];]
{2.5900000000000034`, Null}
T1 == T2
True
Best Regards
Eduardo Feo