Approximation for vertex cover in β -conflict graphs

Conflict graph is a union of finite given sets of disjoint complete multipartite graphs. Vertex cover on this kind of graph is used first to model data inconsistency problems in database application. It is NP-complete if the number of given sets r is fixed, and can be approximated within 2-12r (Miao et al. in Proceedings of the 9th international conference on combinatorial optimization and applications, vol 9486. COCOA 2015, New York. Springer, New York, pp 395–408, 2015). This paper shows a better algorithm to improve the approximation for dense cases. If the ratio of vertex not belongs to any wheel complete multipartite graph is no more than β< 1 , then our algorithm will provide a (1+β+1-βk)-approximation, where k is a parameter related to degree distribution of wheel complete multipartite graph.