Solving Minimum Vertex Cover Problem Using Learning Automata

Aylin Mousavian, Alireza Rezvanian, Mohammad Reza Meybodi

Published:

Minimum vertex cover problem is an NP-Hard problem with the aim of finding
minimum number of vertices to cover graph. In this paper, a learning automaton
based algorithm is proposed to find minimum vertex cover in graph. In the
proposed algorithm, each vertex of graph is equipped with a learning automaton
that has two actions in the candidate or non-candidate of the corresponding
vertex cover set. Due to characteristics of learning automata, this algorithm
significantly reduces the number of covering vertices of graph. The proposed
algorithm based on learning automata iteratively minimize the candidate vertex
cover through the update its action probability. As the proposed algorithm
proceeds, a candidate solution nears to optimal solution of the minimum vertex
cover problem. In order to evaluate the proposed algorithm, several experiments
conducted on DIMACS dataset which compared to conventional methods.
Experimental results show the major superiority of the proposed algorithm over
the other methods.