## iof-tools / networkxMiCe / networkx-master / networkx / algorithms / approximation / independent_set.py @ 5cef0f13

History | View | Annotate | Download (1.98 KB)

1 | 5cef0f13 | tiamilani | ```
# -*- coding: utf-8 -*-
``` |
---|---|---|---|

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 NP-hard 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|/(log|V|)^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) 2011-2012 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 apx-maximum independent set
``` |
||

50 | ```
``` |
||

51 | ```
Notes
``` |
||

52 | ```
-----
``` |
||

53 | ```
Finds the $O(|V|/(log|V|)^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` |