Hardness of Approximating Bounded-Degree Max 2-CSP and Independent Set on k-Claw-Free Graphs
Abstract
We consider the question of approximating 2-CSP where each variable appears in at most d
vertices (but with possibly arbitrarily large alphabet). There is a simple (d/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., TALG 2023], we establish the following hardness results for approximating independent set on k-claw-free graphs:
• Assuming the Unique Games Conjecture (UGC), it is NP-hard (under randomized reduc-
tion) 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 achieves (k/2 − o(k))-approximation in polynomial time [Thiery and Ward, SODA 2023] and (k/3 + O(1))-approximation in quasi-polynomial time [Cygan et al., SODA 2013]
vertices (but with possibly arbitrarily large alphabet). There is a simple (d/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., TALG 2023], we establish the following hardness results for approximating independent set on k-claw-free graphs:
• Assuming the Unique Games Conjecture (UGC), it is NP-hard (under randomized reduc-
tion) 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 achieves (k/2 − o(k))-approximation in polynomial time [Thiery and Ward, SODA 2023] and (k/3 + O(1))-approximation in quasi-polynomial time [Cygan et al., SODA 2013]
