Asymptotically Smaller Encodings for Graph Problems and Scheduling

Bernardo Subercaseaux

We show how several graph problems (e.g., vertex-cover, independent-set, $k$-coloring) can be encoded into CNF using only $O(|V{|}^2/\lg |V|)$ many clauses, as opposed to the $Ω(|V…