Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
Vertex Cover in Conflict Graphs: Complexity and a Near Optimal Approximation
verfasst von : Dongjing Miao, Jianzhong Li, Xianmin Liu, Hong Gao
Erschienen in: Combinatorial Optimization and Applications
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
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 \(\frac{17}{16}-\varepsilon \), for any \(\varepsilon >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-\frac{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.