ioftools / networkxMiCe / networkxmaster / networkx / algorithms / approximation / independent_set.py @ 5cef0f13
History  View  Annotate  Download (1.98 KB)
1 
# * coding: utf8 *


2 
"""

3 
Independent Set

4 

5 
Independent set or stable set is a set of vertices in a graph, no two of

6 
which are adjacent. That is, it is a set I of vertices such that for every

7 
two vertices in I, there is no edge connecting the two. Equivalently, each

8 
edge in the graph has at most one endpoint in I. The size of an independent

9 
set is the number of vertices it contains.

10 

11 
A maximum independent set is a largest independent set for a given graph G

12 
and its size is denoted α(G). The problem of finding such a set is called

13 
the maximum independent set problem and is an NPhard optimization problem.

14 
As such, it is unlikely that there exists an efficient algorithm for finding

15 
a maximum independent set of a graph.

16 

17 
`Wikipedia: Independent set <https://en.wikipedia.org/wiki/Independent_set_(graph_theory)>`_

18 

19 
Independent set algorithm is based on the following paper:

20 

21 
$O(V/(logV)^2)$ apx of maximum clique/independent set.

22 

23 
Boppana, R., & Halldórsson, M. M. (1992).

24 
Approximating maximum independent sets by excluding subgraphs.

25 
BIT Numerical Mathematics, 32(2), 180–196. Springer.

26 
doi:10.1007/BF01994876

27 

28 
"""

29 
# Copyright (C) 20112012 by

30 
# Nicholas Mancuso <nick.mancuso@gmail.com>

31 
# All rights reserved.

32 
# BSD license.

33 
from networkx.algorithms.approximation import clique_removal 
34 
__all__ = ["maximum_independent_set"]

35 
__author__ = """Nicholas Mancuso (nick.mancuso@gmail.com)"""

36  
37  
38 
def maximum_independent_set(G): 
39 
"""Returns an approximate maximum independent set.

40 

41 
Parameters

42 


43 
G : NetworkX graph

44 
Undirected graph

45 

46 
Returns

47 


48 
iset : Set

49 
The apxmaximum independent set

50 

51 
Notes

52 


53 
Finds the $O(V/(logV)^2)$ apx of independent set in the worst case.

54 

55 

56 
References

57 


58 
.. [1] Boppana, R., & Halldórsson, M. M. (1992).

59 
Approximating maximum independent sets by excluding subgraphs.

60 
BIT Numerical Mathematics, 32(2), 180–196. Springer.

61 
"""

62 
iset, _ = clique_removal(G) 
63 
return iset
