Hardness of Approximating Bounded-Degree Max 2-CSP and Independent Set on k-Claw-Free Graphs
share
We consider the question of approximating Max 2-CSP where each variable appears in at most d constraints (but with possibly arbitrarily large alphabet). There is a simple (d+1/2)-approximation algorithm for the problem. We prove the following results for any sufficiently large d: - Assuming the Unique Games Conjecture (UGC), it is NP-hard (under randomized reduction) to approximate this problem to within a factor of (d/2 - o(d)). - It is NP-hard (under randomized reduction) to approximate the problem to within a factor of (d/3 - o(d)). Thanks to a known connection [Dvorak et al., Algorithmica 2023], we establish the following hardness results for approximating Maximum Independent Set on k-claw-free graphs: - Assuming the Unique Games Conjecture (UGC), it is NP-hard (under randomized reduction) to approximate this problem to within a factor of (k/4 - o(k)). - It is NP-hard (under randomized reduction) to approximate the problem to within a factor of (k/3 + 2√(2) - o(k)) ≥(k/5.829 - o(k)). In comparison, known approximation algorithms achieve (k/2 - o(k))-approximation in polynomial time [Neuwohner, STACS 2021; Thiery and Ward, SODA 2023] and (k/3 + o(k))-approximation in quasi-polynomial time [Cygan et al., SODA 2013].
READ FULL TEXT