Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (1.98 KB)

1
# -*- 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