Vertex deletion is a well known NP-complete problem. An empirical method for estimating the number of vertices that need to be deleted to make a graph bipartite is presented. The estimator has been developed by modelling the problem using random graphs where an edge is present with a fixed probability $p$. The method works in $O(n2)$ time, where $n$ is the number of vertices in the graph. The estimator has been experimented on several randomly generated graphs. The results indicate that the estimator gives accurate results for graphs of various sizes.

Keywords:Vertex Deletion, Probabilistic Estimation, NP-complete Problems