Dipartimento di Informatica

Date: Thursday, May 12, 2022
Time: 10:30
Venue: https://meet.google.com/pji-iyvz-tei
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.