Approximation for vertex cover in β -conflict graphs

Dongjing Miao, Zhipeng Cai, Weitian Tong, Jianzhong Li

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish
Pages (from-to)1052-1059
Number of pages8
JournalJournal of Combinatorial Optimization
Volume34
Issue number4
DOIs
StatePublished - Nov 1 2017

Keywords

  • Approximation algorithm
  • Complete multipartite graph
  • Conflict graph
  • Vertex cover

Fingerprint

Dive into the research topics of 'Approximation for vertex cover in β -conflict graphs'. Together they form a unique fingerprint.

Cite this