The paper presents an algorithm for nding the maximum independent set in an undirected graph with absolute estimate of the accuracy. Special notions are indroduced and theoretical results in the area of deviation of approximate solution from the exact one are presended. Also the paper presents results of computational experiments on the complementary graphs DIMACS.
The problem of the maximum independent set of vertices in an undirected graph (MIS Problem) has applications in many areas. So, for example, the vertices of the social graph can be interpreted as users accounts. In this case, the independent set will correspond to di erent accounts, and the clique in the complementary garph will correspond to fake ones. Another example is the location of enterprises. In this context, the independent set will correspond to the optimal location. Thus, the relevance of the research does not cause doubts in terms of practical signi cance.
MIS Problem is a classical N P{hard. In complexity theory 3-satis ability problem (3-SAT) reduces to it, which in turn reduces to the standard hard satis ability problem (SAT). This e ect indicates that the problem under consideration have special scienti c interest. As it is known, for today the problem of Copyright c by the paper's authors. Copying permitted for private and academic purposes.
In: S. Belim et al. (eds.): OPTA-SCL 2018, Omsk, Russia, published at http://ceur-ws.org
equality of classes is not solved and there is no polynomial algorithm for any hard
problem. In this connection, approximate and heuristic algorithms are
developing actively. The disadvantage of approximate algorithms is that estimates of the
accuracy obtained are usually greatly overstated. So, for example, in [
In [
The Maximum Independent Set in the Graph Let us consider an undirected graph G = (V; E ), in which is the set of vertices, and is the set of edges.
V = fvi ; i = [n]g
E = fe = (vi; vj ) ; i; j 2 [n]g De nition 1. For an integer k 2 [n 1] we call a vertex v 2 V of the graph G = (V; E ) a k{vertex if jN (v)j = k and the neighborhood of this vertex is the complete induced subgraph.
De nition 2. For integers k 2 [n 1] and m we call a vertex v 2 V of the graph G = (V; E ) a (k; m){vertex if k = jN (v)j and in the neighborhood of this vertex there are absent m edges to be the complete induced subgraph. Proposition 1. If the vertex v is a k{vertex in the undirected graph G = (V; E ) then there exists the maximum independent set of vertices S V such that v 2 S.
Proof. Let us consider the arbitrary maximum independent set S of the graph and the k{vertex v 2 V . It is easy to see that among elements of the set fvg [ N (v) set there is vertex u such that u 2 S. Indead otherwise one could nd an independent set S0 V such that S0 = fvg [ S and jS0j > jSj.This contradicts the maximality of the independent set S.
Now let us consider two possible cases. 1) If v 2 S then we are done. 2) If v 62 S and u 2 S for some vertex u 2 N (v) then for S one can nd the
S0 = S fug [ fvg which is also the independent set by de nition of k-vertex. By construction we have jS0j = jSj. Thus we obtained the maximum independent set S0 such that v 2 S0 as was to be proved.
Note that Proposition 1 underlies the idea of developing the heuristic algorithm with the absolute estimate of the accuracy. 3
The Algorithm for MIS Problem with Absolute Estimate of the Accuracy We denote the set of all independent sets of the graph G as S (G) and the set of all maximum independent sets of the graph G as Smax (G). Let max S (G) = jSj: S 2 Smax (G) be the cardinality of the maximum independent set of the graph G.
Proposition 2. Let two graphs G1 = (V1; E1) and G2 = (V2; E2) are such that V1 = V2, and E1 E2. Then
S (G1) : Proof. Consider an arbitrary independent set S 2 S (G2) of the graph G2. By the de nition of the independent set we have:
8 u; v 2 V2: u; v 2 S (u; v) 62 E2 :
By the hypothesis of the proposition, we have E1 consequence for any S 2 S (G2) we have
E2 and V1 = V2. As a 8 u; v 2 V2: u; v 2 S (u; v) 62 E1 : and thus (1)
S 2 S (G1) : S (G2)
S (G1) :
Then for any set of vertices of the graph G such that S 2 S (G2), the inclusion (1) holds, that is, At the same time by de nition of the maximum independent set of the graph, we have that any maximum independent set of the graph is clearly the independent set of the graph, so
S (G2)
S (G1) ; as was to be proved.
Corollary 1. Let G1 = (V; E1) and G2 = (V; E2) be graphs such that E1 Then E2. max S (G1) max S (G2) : Proof. Let us consider the maximum independent set S 2 Smax (G2). According to Proposition 2 we have S 2 S (G1). By de nition for any S 2 S (G1) there exists S0 2 Smax (G1) such that jS0j jSj. Then
max S (G1) = jS0j jSj = max S (G2) ;
The following proposition underlies the absolute estimate of the accuracy of the approximate solution.
Proposition 3. Let G = V; E be a graph in which vertices v and u are not adjacent. And let G0 = (V 0; E0) be a graph in which V 0 = V and E0 = E [f(v; u)g. Then max S (G) max S (G0) Proof. The inequality max S (G) max S (G0) follows from Corollary 1 since E E0. Let us prove the inequality max S (G0) max S (G) 1. Let S be the maximum independent set of the graph G.
1) Suppose that v 62 S and u 62 S. Then S 2 Smax (G0). Indead otherwise we would obtain that there exists the maximum independent set S0 2 Smax (G0) such that jS0j > jSj. According to Proposition 1, we obtain that S0 2 S (G), but this contradicts the maximality of the set S under consideration. Thus, in this case, we have: max S (G) = jSj = max S (G0) 2) Suppose that v 2 S and u 62 S. If the edge (v; u) is added, then S 2 Smax (G0) as was shown above.
3) Suppose that v 2 S and u 2 S. If the edge (v; u) is added, then we obtain S 62 Smax (G0). In this case we can nd a set S0 such that S0 = S fvg. Then S0 2 Smax (G0) and jS0j = jSj by construction. By the de nition of the maximum independent set of the graph, we have: max S (G0) jS0j = jSj 1 = max S (G) 1 ;
Corollary 2. Let fe1; : : : ; ekg be a subfamily of k vertex pairs that are not edges of the graph G = (V; E). And let the graph G0 = (V 0; E0) is such that V 0 = V and E0 = E [ fe1; : : : ; ekg. Then max S (G)
k : Proof. For proof it su ces to apply Proposition 3 k times.
Proposition 4. If the vertex v is a (k; m){vertex in the graph G = (V; E ) then there exists a maximal independent set S V such that v 2 S and jSj Proof. According to de nition there are missed m edges in the neighborhood of the vertex v to be the complete induced subgraph. Suppose these edges are fe1; : : : ; emg. Then the vertex v is a k{vertex in the graph G0, which is obtained from the graph G by the addition of these m edges fe1; : : : ; emg. According to Proposition 1 there exists S0: S0 2 Smax (G0) such that v 2 S0.
According to Corollary 2 we have: jS0j = max S (G0) It follows from Proposition 2 that S0 2 S (G). By de nition there exists a maximal independent set S such that jSj jS0j and, as a consequence jSj jS0j 1: V0 V fthe current set of vertices consists of applicants for inclusion in the independent setg 2: S fg 3: Est 0 4: while V0 6= fg do 5: for all v 2 V0 do 6: calculate k[v] 7: calculate m[v] 8: end for 9: v0 M inM axP aram (v) 10: S S [ fv0g 11: Est Est + m[v0] 12: V0 V0 fv0g N (v0; V0)fremove from the set of applicants the selected vertex together with neighborhoodg 13: end while
This algorithm was implemented and used to nd the maximum independent set in complementary graphs DIMACS. It is clear that in the initial graph the solution obtained will correspond to the clique. Then it became possible to compare results with other e ective algorithms. 3.1
The following corollary shows that in some cases the Algorithm B (G) allows to nd the exact solution of the MIS Problem.
Corollary 3. If Est = 0 then the independent set S found by Algorithm B (G) is the maximum.
Proof. If Est = 0 then m[v] = 0 for all v 2 S. This means that all these vertices are k{vertices. Thus, according to Proposition 1 the independent set obtained is the maximum.
It is clear that Est = 0 is not always satis ed. This motivates to study particular classes of graphs for which the condition of the Corollary 3 hold. Proposition 5. For any connected graph G = (V; E ), where jV j > 2, there exists the maximum independent set that contains all hanging vertices of this graph. Proof. Consider the connected graph G = (V; E ), where jV j > 2. Let v 2 V be hanging vertex. Implementation of the algorithm B (G) allows di erent states of V0. Let's consider each of them in detail.
1) The vertex v is a hanging and unique k{vertex. Then S S [ fvg as required.
2) The vertex v is a hanging and not unique k{vertex. Consider the vertex u adjacent to the hanging vertex v. The vertex u can not be included in the set S at the rst step, since the neighborhood of the vertex u is not the complete induced subgraph. Indead the vertex v is hanging and adjacent to u, that is the vertex v is in the neighborhood of the vertex u. The graph G = (V; E) is connected, then in the neighborhood of the vertex u (in the rst step, when V0 coincides with V ) there are also other vertices . But the vertex v can not be adjacent to any of them, since deg (v; V0) = 1 and the vertex adjacent to v is the vertex u. Thus, the vertex u is not a k{vertex and will not be included in S on the rst step of the algorithm.
A similar situation occurs at any step if at least one vertex remains in the neighborhood of the vertex u except for the hanging vertex v. Vertices in the neighborhood of the vertex u will still not be adjacent, and therefore the vertex u will not be a k{vertex.
Let at some step all vertices adjacent to u be removed except for the hanging vertex v. This can happen when vertices adjacent to vertices from the neighborhood of the vertex u will be included in S. In this situation the vertex u becomes a k{vertex and can be included in S. However, the vertex v can also be included in S, which does not reduce the cardinality of S.
Indeed, let s: jSj = s be the cardinality of S at some step. And let the vertex u be included in S and the vertex v be not included, then
S S
S [ fug =) jSj = s + 1 :
S [ fvg =) jSj = s + 1 ;
Now suppose that the vertex v be included in S and the vertex u be not included, then that is, one can include the hanging vertex without decreasing the cardinality of the independent set. Note that if the above situation occurs, then all vertices which are included in S are k{vertices. Thus, according to Corollary 3 there exists the maximum independent set of vertices which contains the hanging vertex v.
Arguing similarly for each hanging vertex we get what was required to prove.
Thus, we can formulate a more general proposition about the Algorithm B (G). Proposition 6. The Algorithm B (G) implemented in the class of trees allows to nd the exact solution of the MIS Problem.
Proof. According to Corollary 3 the independent set found by the Algorithm B (G) is maximum if Est = 0. In the case when initial graph is a tree at each step its hanging (or isolated) vertices could be included in S. In this way Est = P m[v] = 0 and the independent set S is the maximum as required.
v2S
Note that Proposition 6 is the property of the Algorithm B (G). In addition to
this algorithm, the method of dynamic programming from [
Let us discuss the algorithmic complexity of the Algorithm B (G).
For each vertex v it is necessary to nd the number of vertices in the neighborhood and the number of edges that should be added. We remove the vertices v [ N (v; V0) and the edges e 2 Ghfvg [ N (v; V0)i until V0 becomes empty. Let n and m be the number of vertices and the number of edges of the initial graph respectivle.
Then we obtain the following estimate. The common number of iterations is less than or equal to n. Each iteration needs no more than O (n m) actions to calculate parameters and no more than O (m) actions to remove selected vertex together with neighborhood. Thus, the complexity of the Algorithm B (G) is O (n n m + n m) = O n2 m . 4
Computational Results
The table below shows the results of computational experiments with
complementary graphs DIMACS. The table gives the results of the comparison with
e ective algorithms from [
In the column ! (G) there is maximal clique of the coresponding graph, and the exact solution (maximum clique) is highlighted in bold. In the column B (G) the results for proposed heuristic algorithm are given.
It can be seen that the best{known solutuion was obtained in some cases only but the approximate solution is rather close to the best{known or exact ones. Furthermore, the algorithm shows high e ciency in terms of time complexity of calculations. The paper presents the algorithm for MIS Problem with the absolute estimate of the accuracy of the approximate solution. Special notions were indroduced and theoretical results of research were presended. The properties of the algorithm are investigated and, in particular, its convergence in the class of trees is shown. The results of computational experiments on complementary graphs DIMACS are presented, which demonstrate rather good results in terms of the quality of the approximate solution and high e ciency in terms of the time complexity of the calculations.
Acknowledgement. The results of the work were obtained within the framework of the state task of the Ministry of Education and Science of RF no. 2.2461.2017/4.6.