2026-08-10T23:04:13Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10825 2024-03-06T10:46:48Z ddc:004 open_access

UG-Hardness to NP-Hardness by Losing Half Bhangale, Amey Khot, Subhash NP-hardness Inapproximability Unique Games Conjecture The 2-to-2 Games Theorem of [Subhash Khot et al., 2017; Dinur et al., 2018; Dinur et al., 2018; Dinur et al., 2018] implies that it is NP-hard to distinguish between Unique Games instances with assignment satisfying at least (1/2-epsilon) fraction of the constraints vs. no assignment satisfying more than epsilon fraction of the constraints, for every constant epsilon>0. We show that the reduction can be transformed in a non-trivial way to give a stronger guarantee in the completeness case: For at least (1/2-epsilon) fraction of the vertices on one side, all the constraints associated with them in the Unique Games instance can be satisfied. We use this guarantee to convert the known UG-hardness results to NP-hardness. We show: 1) Tight inapproximability of approximating independent sets in degree d graphs within a factor of Omega(d/(log^2 d)), where d is a constant. 2) NP-hardness of approximate the Maximum Acyclic Subgraph problem within a factor of 2/3+epsilon, improving the previous ratio of 14/15+epsilon by Austrin et al. [Austrin et al., 2015]. 3) For any predicate P^{-1}(1) subseteq [q]^k supporting a balanced pairwise independent distribution, given a P-CSP instance with value at least 1/2-epsilon, it is NP-hard to satisfy more than (|P^{-1}(1)|/(q^k))+epsilon fraction of constraints. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Amey Bhangale and Subhash Khot 2019 Is Part Of LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2019.3 urn:nbn:de:0030-drops-108258 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.3 eng https://creativecommons.org/licenses/by/3.0/legalcode