Approximating Maximum Weighted Independent Set Using Vertex Support

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.

Authors:

• S. Balaji
• V. Swaminathan
• K. Kannan

Keywords:

• weighted independent set
• vertex cover
• vertex support
• heuristic
• NP - hard problem.

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.