Approximation algorithms for vertex cover problems in hypergraphs
Date: Thursday, May 12, 2022
Speaker: Tony Huynh
Title: Approximation algorithms for vertex cover problems in hypergraphs
Abstract: Many optimization problems can be phrased as a vertex cover problem in a k-uniform hypergraph. For example, feedback vertex set in tournaments (FVST), split graph deletion (SVD), and cluster vertex deletion (CVD) are three such problems. Assuming the Unique Games Conjecture, none of these three problems can be solved efficiently within a factor better than 2. We present a 7/3-approximation algorithm for FVST, a (2 + ε)-approximation algorithm for SVD, and a 2-approximation algorithm for CVD.