Home > CSC-OpenAccess Library > Manuscript Information

This is an Open Access publication published under CSC-OpenAccess Policy.

A Fast Near Optimal Vertex Cover Algorithm (NOVCA)

Sanjaya Gajurel, Roger Bielefeld

Pages - 9 - 18 | Revised - 15-09-2012 | Published - 25-10-2012

MORE INFORMATION

KEYWORDS

Vertex Cover Problem, Combinatorial Problem, NP-Complete Problem, Approximation Algorithm

ABSTRACT

This paper describes an extremely fast polynomial time algorithm, the Near Optimal Vertex Cover Algorithm (NOVCA) that produces an optimal or near optimal vertex cover for any known undirected graph G (V, E). NOVCA is based on the idea of (i) including the vertex having maximum degree in the vertex cover and (ii) rendering the degree of a vertex to zero by including all its adjacent vertices. The two versions of algorithm, NOVCA-I and NOVCA-II, have been developed. The results identifying bounds on the size of the minimum vertex cover as well as polynomial complexity of algorithm are given with experimental verification. Future research efforts will be directed at tuning the algorithm and providing proof for better approximation ratio with NOVCA compared to any other available vertex cover algorithms.

1 | Eshtay, M., Sliet, A., & Sharieh, A. NMVSA Greedy Solution for Vertex Cover Problem. vertex, 2, 15. |

2 | Gajurel, S., Cleveland, U. S., & Bielefeld, R. (2015, September). Mutated Near Optimal Vertex Cover Algorithm (NOVCA) Visualization on a Tile Display. In Cluster Computing (CLUSTER), 2015 IEEE International Conference on (pp. 525-526). IEEE. |

3 | Gajurel, S., & Bielefeld, R. (2014). A Heuristic Approach to Fast NOVCA (Near Optimal Vertex Cover Algorithm). Computer Technology and Application, 5(2). |

4 | Cai, S., Su, K., Luo, C., & Sattar, A. (2013). NuMVC: An efficient local search algorithm for minimum vertex cover. Journal of Artificial Intelligence Research, 687-716. |

1 | Google Scholar |

2 | CiteSeerX |

3 | refSeek |

4 | Scribd |

5 | SlideShare |

6 | PdfSR |

1 | R. Karp. “Reducibility among combinatorial problems”. In R. E. Miller and J. W. Thatcher(eds.). Complexity of Computer Computations, Plenum Press, NY, pp. 85-103, 1972. |

2 | T. Cormen, C. Leiserson, R. Rivest. Introduction to Algorithms. The MIT Press, pp. 1022-1024, 2001. |

3 | R. Bar-Yehuda and S. Even. “A local-ratio theorem for approximating the weighted vertex cover problem”. North-Holland Mathematics Studies, vol. 109, pp. 27-45, 1985. |

4 | B. Monien and E. Speckenmeyer. “Ramsey numbers and an approximation algorithm for the vertex cover problem”. Acta Informatica, vol. 22, pp. 115-123, 1985. |

5 | E. Halperin. “Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs”. SIAM J. on Computing, vol. 31, pp. 1608-1623, 2002. Also in Proc. of 11th SODA, pp. 329-337, 2000. |

6 | G. Karakostas. “A better approximation ratio for the vertex cover problem”. ICALP, pp.1043-1050, 2005. |

7 | G. Rudolph. “Finite Markov chain results in evolutionary computation”. A tour d’horizon,Fundamenta Informaticae, vol. 35, pp. 67-89, 1998. |

8 | P. Oliveto, J. He, X. Yao. “Evolutionary algorithms and the Vertex Cover problem”. CEC,pp. 1430-1438, 2007. |

9 | J. Chen, I. Kanj and G. Xia. “Simplicity Is Beauty: Improved Upper Bounds for Vertex Cover”. Technical report TR05-008, School of CTI, DePaul University, 2005. |

10 | F. Abu-Khazm, M. Fellows, M. Langston, and W. Suters. “Crown Structures for Vertex Cover Kernelization”. Theory Comput. Systems, vol. 41, pp. 411-430, 2007. |

11 | E. Asgeirsson and C. Stein. “Vertex Cover Approximation on Random Graphs”. WEA 2007, LNCS 4525, pp. 285–296, 2007. |

12 | I. Dinur and S. Safra. “The importance of being biased”. STOC’02, pp. 33-42, 2002. |

13 | NWB Team. Network Workbench Tool. Indiana University, North Eastern University, and University of Michigan, http://nwb.slis.indiana.edu/, 2006. |

14 | S. Gajurel, R. Bielefeld. “A Simple NOVCA: Near Optimal Vertex Cover Algorithm”.Procedia Computer Science, vol. 9, pp 747-753, 2012. |

15 | K. Xu. “Vertex Cover Benchmark Instances (DIMACS and BHOSLIB)”.http://www.cs.hbg.psu.edu/benchmarks/vertex_cover.html, 2012. |

16 | S. Richter, M. Helmert, and C. Gretton. “A Stochastic Local Search Approach to Vertex Cover”. In Proceedings of the 30th German Conference of Artificial Intelligence (KI), pp 412-426, 2007. |

17 | S. Cai, K. Su and A. Sattar. “Local Search with Edge Weighting and Configuration Checking Heuristics for Minimum Vertex Cover”. Artif. Intell., vol. 175 pp. 1672-1696,2011. |

18 | W. Pullan. “Phased Local Search for the Maximum Clique Problem”. J. Comb. Optim.,vol. 12, pp. 303-323, 2006. |

Dr. Sanjaya Gajurel

Case Western Reserve University - United States of America

sxg125@case.edu

Dr. Roger Bielefeld

Case Western Reserve University - United States of America