A probabilistic estimator for the vertex deletion problem

✍ Scribed by C.A. Mandal; P.P. Chakrabarti; S. Ghose

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 264 KB
• Volume: 35
• Category: Article
• ISSN: 0898-1221
• DOI: 10.1016/s0898-1221(98)00012-1

✦ Synopsis

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(n 2) 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.

By definition, the expected number of vertices E(d) to be deleted to render graphs of the type Gn,p bipartite is Typeset by A h~TEX