Although much of this work has focused on independent sets in sparse graphs, a case that does not make sense for the complementary clique problem, there has also been work on approximation algorithms that do not use such sparsity assumptions.
Deși o mare parte din această muncă s-a concentrat pe mulțimi independente în grafuri rare, un caz care nu are sens pentru problema complementară a clicii, s-a lucrat și la algoritmi de aproximare care nu folosesc astfel de prezumții de raritate.