Independent set, vertex cover, k-coloring and clique admit CNF encodings with O(n^2/log n) clauses, and the disjoint-intervals encoding needs only O(n^2 log n) clauses.
Covering the edges of a random graph by cliques
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
The clique cover number of a graph G is the minimum number of cliques required to cover the edges of graph G. In this paper we consider the random graph G(n,p), for p constant. We prove that with probability 1-o(1), the clique number of G(n,p) is Theta(n^2/\log^2n).
citation-role summary
method 1
citation-polarity summary
fields
cs.LO 1years
2025 1verdicts
CONDITIONAL 1roles
method 1polarities
use method 1representative citing papers
citing papers explorer
-
Asymptotically Smaller Encodings for Graph Problems and Scheduling
Independent set, vertex cover, k-coloring and clique admit CNF encodings with O(n^2/log n) clauses, and the disjoint-intervals encoding needs only O(n^2 log n) clauses.