Vertex Cover in Conflict Graphs: Complexity and a Near Optimal Approximation

Given finite number of forests of complete multipartite graph, conflict graph is a sum graph of them. Graph of this class can model many natural problems, such as in database application and others. We show that this property is non-trivial if limiting the number of forests of complete multipartite graph, then study the problem of vertex cover on conflict graph in this paper. The complexity results list as follow, - If the number of forests of complete multipartite graph is fixed, conflict graph is non-trivial property, but finding 1.36-approximation algorithms is NP-hard. - Given 2 forests of complete multipartite graph and maximum degree less than 7, vertex cover problem of conflict graph is NP-complete. Without the degree restriction, it is shown to be NP-hard to find an algorithm for vertex cover of conflict graph within 17/16 - epsilon, for any epsilon > 0. Given conflict graph consists of r forests of complete multipartite graph, we design an approximation algorithm and show that the approximation ratio can be bounded by 2 - 1/2(r). Furthermore, under the assumption of UGC, the approximation algorithm is shown to be near optimal by proving that, it is hard to improve the ratio with a factor independent of the size (number of vertex) of conflict graph.