TABARIS: An exact algorithm based on tabu search for finding a maximum independent set in a graph (Q750320)

In an arbitrary graph G a subset S of nodes is independent if no two nodes of S are linked by an edge of G; and S is independent in G if and only if it is a clique in the complement \(\bar G\) of G. This gives rise to the difficult problem to find in G an independent set with maximum cardinality. Already several exact procedures for graphs of moderate size are known, especially the Balas-Yu algorithm. In the present paper a further algorithm is developed which is an exact implicit enumeration procedure, which uses bounds on the independence number of a subgraph and which is also applicable to graphs of larger size. To find such bounds Tabu Search (TS) techniques are used, and the general method of TS is described in Table 2. The new algorithm is called TABARIS (Tabu And Branch and Bound Applied Repeatedly for Independent Sets); its general procedure is described in detail in a formalized manner (Table 1) and among other things it contains the solution of the following two problems which imply the above mentioned specializations of TS: (1) Finding a large stable set; (2) covering a large node set with certain cliques. These steps and their algorithms are again stated in a formalized manner by tables and the solution of (1) is accomplished by a heuristic procedure which is called STABULARGE (Table 3). To solve (2) three sequential algorithms are given, which are formulated in Tables 4 and 5. - Computational experiments have been performed on random graphs with 40- 400 nodes and with densities between 0.1 and 0.9; the obtained results by applying TABARIS and the Balas-Yu algorithm both are compared and analyzed (Table 6). Finally TABARIS was applied to random graphs with 450 nodes (density 0.5), to one graph with 500 nodes (density 0.5) and to one graph with 1000 nodes (density 0.7) and the results reported in Table 7.