Approximating Maximum Weighted Independent Set Using Vertex Support

Authors: S. Balaji, V. Swaminathan, K. Kannan

Abstract:

The Maximum Weighted Independent Set (MWIS) problem is a classic graph optimization NP-hard problem. Given an undirected graph G = (V, E) and weighting function defined on the vertex set, the MWIS problem is to find a vertex set S V whose total weight is maximum subject to no two vertices in S are adjacent. This paper presents a novel approach to approximate the MWIS of a graph using minimum weighted vertex cover of the graph. Computational experiments are designed and conducted to study the performance of our proposed algorithm. Extensive simulation results show that the proposed algorithm can yield better solutions than other existing algorithms found in the literature for solving the MWIS.

Keywords: weighted independent set, vertex cover, vertex support, heuristic, NP - hard problem.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1078659

References:

[1] L. Babel: A fast algorithm for the maximum weight clique problem, Computing, (1994), Vol. 52, pp. 31-38.
[2] S.Balaji, V. Swaminathan & K. Kannan: An Effective Algorithm for Minimum Weighted Vertex Cover problem, to be appear in International Journal of Computational and Mathematical Sciences, Vol.4 (1) (2010), pp. 34-38.
[3] B. Bollobas: Random graphs (2nd Ed.). Cambridge, UK: Cambridge University press (2001)
[4] I. Bomze, M. Budinich, M. Pellilo & Rossic: Annealed Replication: A new heuristic for the maximum clique problem, Discrete Applied Mathematics, (2002), Vol. 121, pp. 27-49.
[5] I. Bomze, M. Pellilo & V. Stix: Approximating the maximum weight clique using replicator dynamics, IEEE Transactions Neural Network, (2000), vol. 11.
[6] P. Crescenzi, C. Fiorini & R. Silvestri: A note on the approximation of the max. clique problem, Information Processing Letters, (1991), vol. 40, No.1, pp. 1-5.
[7] S. De Vries & R. Vohra: Combinatorial auctions: a survey, INFORMS Journal on Computing (2003), vol. 15, pp. 284-309.
[8] DIMACS clique benchmarks, Benchmark instances made available by electronic transfer at dimacs.rutgers.edu, Rutgers Univ., Piscataway. NJ. (1993).
[9] T. Etzion & P. R. J. stergrd: Greedy and heuristic algorithms for codes and colorings, IEEE Transactions on Information Theory, (1998), vol. 44, pp. 382-388.
[10] U. Feige, S. Goldwasser, L. Lovasz, S. Safra & M. Szegedy: Approximating clique is almost NP-complete, Proceedings of the 32nd IEEE Annual symposium on Foundations of computer science, San Juan, Paerto Rico, (1991), pp. 2 -12.
[11] E. J. Gardiner, P. J. Artymink & P. Willett: Clique detection algorithms for matching three-dimensional structures, Journal of Molecular Graphics and Modeling, (1998), vol. 15, pp. 245-253.
[12] M. R. Garey, D. S. Johnson: Computers and Intractability: A Guide to the theory NP - completeness, San Francisco: Freeman (1979).
[13] A. Mehrotra & M. A. Trick: A Column generation approach for graph coloring, INFORMS Journal on Computing (1996), vol. 8, pp. 344-354.
[14] P R J Ostergard: A New Algorithm for the Maximum Weight Clique problem, Nordic Journal of Computing, (2001), vol. 8, pp 424-436.
[15] P. Pardolos & J. Xue: The maximum clique problem, Journal of Global optimization, (1994), vol.4, pp. 301-328.
[16] P. A. Pevzner & S. H. Sze: Combinatorial approaches to finding subtle signals in DNA sequences, Proceedings of Eighth International Conference on intelligent systems for Molecular Biology, AAAI Press, (2000), pp.269-278.
[17] W. Pullan: Approximating the maximum vertex/edge weighted clique using local search, Jounal of Heuristics, (2008), vol. 14, pp. 117-134.
[18] W. Pullan: Optimisation of unweighted/weighted maximum independent sets and minimum vertex covers, Discrete Optimization, (2009), vol. 6, pp. 214-219.
[19] M. Weight & A. K. Hartmann: Minimal vertex covers on finiteconnectivity random graphs - A hard-sphere lattice-gas picture, Phys. Rev. E, 63, 056127.