In this paper we will be concerned with a large class of packing
and covering problems which includes Vertex Cover and Independent Set.
Typically, for NP-hard problems among them, one can write an LP relaxation and
then round the solution. For instance, for Vertex Cover, one can obtain a
2-approximation via this approach. On the other hand, Khot and Regev proved
that, assuming the Unique Games Conjecture (UGC), it is NP-hard to approximate
Vertex Cover to within a factor better than $2-\varepsilon$ for any constant
$\varepsilon>0$. From their, and subsequent proofs of this result, it was not clear
why this LP relaxation should be optimal.

The situation was akin to Maximum Cut, where a natural SDP relaxation for it
was proved by Khot et. al. to be optimal assuming the UGC. A beautiful result
of Raghavendra explains why the SDP is optimal (assuming the UGC). Moreover,
his result generalizes to a large class of constraint satisfaction
problems (CSPs). Unfortunately, we do not know how to extend his framework
so that it applies for problems such as Vertex Cover where the constraints
are strict.

In this paper, we explain why the simple {LP}-based rounding algorithm for
the Vertex Cover problem is optimal assuming the UGC. Complementing
Raghavendra's result, our result generalizes to a larger class of strict,
covering/packing type CSPs. We first write down a natural LP relaxation for
this class of problems and present a simple rounding algorithm for it. The
key ingredient, then, is a dictatorship test, which is parametrized by a
rounding-gap example for this LP, whose completeness and soundness are the
LP-value and the rounded value respectively. To the best of our knowledge,
ours is the first result which proves the optimality of LP-based rounding
algorithms systematically.

Added a section on extension of our results to q-ary alphabets.

In this paper we will be concerned with a large class of packing
and covering problems which includes Vertex Cover and Independent Set.
Typically, for NP-hard problems among them, one can write an LP relaxation and
then round the solution. For instance, for Vertex Cover, one can obtain a
2-approximation via this approach. On the other hand, Khot and Regev proved
that, assuming the Unique Games Conjecture (UGC), it is NP-hard to approximate
Vertex Cover to within a factor better than $2-\varepsilon$ for any constant
$\varepsilon>0$. From their, and subsequent proofs of this result, it was not clear
why this LP relaxation should be optimal.

The situation was akin to Maximum Cut, where a natural SDP relaxation for it
was proved by Khot et. al. to be optimal assuming the UGC. A beautiful result
of Raghavendra explains why the SDP is optimal (assuming the UGC). Moreover,
his result generalizes to a large class of constraint satisfaction
problems (CSPs). Unfortunately, we do not know how to extend his framework
so that it applies for problems such as Vertex Cover where the constraints
are strict.

In this paper, we explain why the simple {LP}-based rounding algorithm for
the Vertex Cover problem is optimal assuming the UGC. Complementing
Raghavendra's result, our result generalizes to a larger class of strict,
covering/packing type CSPs. We first write down a natural LP relaxation for
this class of problems and present a simple rounding algorithm for it. The
key ingredient, then, is a dictatorship test, which is parametrized by a
rounding-gap example for this LP, whose completeness and soundness are the
LP-value and the rounded value respectively. To the best of our knowledge,
ours is the first result which proves the optimality of LP-based rounding
algorithms systematically.