A well-studied variant of CSPs are CSPs with cardinality constraints i.e., CSPs where there are global constraints on the relative weight of vertices that can be assigned a particular label. Perhaps one of the simplest instantiations of a CSP with a cardinality constraint is the Densest-\(k\) -Subgraph (D\(k\) S) problem. Here, given an undirected graph \(G = (V,E)\)  and a parameter \(k \in \mathbb {N}\) , the objective is to find a subset of \(k\) -vertices such that the number edges induced by the subset is maximized. It is easy to see that this is an instantiation of a Boolean CSP of arity 2 with the underlying graph as \(G\) , the edge constraints being AND, and the global cardinality constraint is that exactly \(k\)  vertices of the CSP can be assigned the label 1. Furthermore, this is also a relaxation of the \(k\) -Clique problem, and consequently, it is not surprising that there has been many works which study its approximability [1]}, [2]}, [3]}, [4]}.
