A characterization of approximability for biased CSPs

DOI10.1145/3519935.3520072MaRDI QIDQ6083553zbMATH OpenFDO

Authors Euiwoong Lee, Suprovat Ghoshal

Publication date 8 December 2023

Published in Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2201.04617

zbMATH Keywords

constraint satisfaction problemsdensest-\(k\)-subhypergraphinapproximability

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: A $mu$-biased Max-CSP instance with predicate $psi:{0,1}^{r}o0,1$ is an instance of Constraint Satisfaction Problem (CSP) where the objective is to find a labeling of relative weight at most $mu$ which satisfies the maximum fraction of constraints. Biased CSPs are versatile and express several well studied problems such as Densest-$k$-Sub(Hyper)graph and SmallSetExpansion. In this work, we explore the role played by the bias parameter $mu$ on the approximability of biased CSPs. We show that the approximability of such CSPs can be characterized (up to loss of factors of arity $r$) using the bias-approximation curve of Densest-$k$-SubHypergraph (DkSH). In particular, this gives a tight characterization of predicates which admit approximation guarantees that are independent of the bias parameter $mu$. Motivated by the above, we give new approximation and hardness results for DkSH. In particular, assuming the Small Set Expansion Hypothesis (SSEH), we show that DkSH with arity $r$ and $k=mun$ is NP-hard to approximate to a factor of $Omega(r^{3}m{u}^{r-1}log(1/mu))$ for every $rgeq2$ and $mu<2^{-r}$. We also give a $O(m{u}^{r-1}log(1/mu))$-approximation algorithm for the same setting. Our upper and lower bounds are tight up to constant factors, when the arity $r$ is a constant, and in particular, imply the first tight approximation bounds for the Densest-$k$-Subgraph problem in the linear bias regime. Furthermore, using the above characterization, our results also imply matching algorithms and hardness for every biased CSP of constant arity.

Recommendations

• The complexity of approximating bounded-degree Boolean \#CSP
• Approximating the bipartite TSP and its biased generalization
• The complexity of approximating bounded-degree Boolean \(\#\)CSP
• An approximation trichotomy for Boolean \#CSP
• scientific article; zbMATH DE number 2086657
• Towards a characterization of approximation resistance for symmetric CSPs
• Towards a characterization of approximation resistance for symmetric CSPs
• Complexity of approximating CSP with balance/hard constraints

Cited in

(2)

• Optirefine: densest subgraphs and maximum cuts with k refinements
• Optimizing alphabet reduction pairs of arrays

This page was built for publication: A characterization of approximability for biased CSPs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6083553)