### comparison env/lib/python3.9/site-packages/networkx/algorithms/approximation/independent_set.py @ 0:4f3585e2f14bdraftdefaulttip

author shellac Mon, 22 Mar 2021 18:12:50 +0000
comparison
equal inserted replaced
-1:000000000000 0:4f3585e2f14b
1 r"""
2 Independent Set
3
4 Independent set or stable set is a set of vertices in a graph, no two of
5 which are adjacent. That is, it is a set I of vertices such that for every
6 two vertices in I, there is no edge connecting the two. Equivalently, each
7 edge in the graph has at most one endpoint in I. The size of an independent
8 set is the number of vertices it contains.
9
10 A maximum independent set is a largest independent set for a given graph G
11 and its size is denoted $\alpha(G)$. The problem of finding such a set is called
12 the maximum independent set problem and is an NP-hard optimization problem.
13 As such, it is unlikely that there exists an efficient algorithm for finding
14 a maximum independent set of a graph.
15
16 Wikipedia: Independent set <https://en.wikipedia.org/wiki/Independent_set_(graph_theory)>_
17
18 Independent set algorithm is based on the following paper:
19
20 $O(|V|/(log|V|)^2)$ apx of maximum clique/independent set.
21
22 Boppana, R., & Halldórsson, M. M. (1992).
23 Approximating maximum independent sets by excluding subgraphs.
24 BIT Numerical Mathematics, 32(2), 180–196. Springer.
25 doi:10.1007/BF01994876
26
27 """
28 from networkx.algorithms.approximation import clique_removal
29
30 __all__ = ["maximum_independent_set"]
31
32
33 def maximum_independent_set(G):
34 """Returns an approximate maximum independent set.
35
36 Parameters
37 ----------
38 G : NetworkX graph
39 Undirected graph
40
41 Returns
42 -------
43 iset : Set
44 The apx-maximum independent set
45
46 Notes
47 -----
48 Finds the $O(|V|/(log|V|)^2)$ apx of independent set in the worst case.
49
50
51 References
52 ----------
53 ..  Boppana, R., & Halldórsson, M. M. (1992).
54 Approximating maximum independent sets by excluding subgraphs.
55 BIT Numerical Mathematics, 32(2), 180–196. Springer.
56 """
57 iset, _ = clique_removal(G)
58 return iset