1
$\begingroup$

Some definitions, just to not create confusion:

  1. A sparse graph is a graph that contains a number of edges less or equal than the number of vertices.

  2. In $k$-clique problem we are given a graph and an integer $k$, and the task is to decide whether the graph contains a $k$-clique.

I think that even if we have a sparse graph, nothing changes for the $k$-clique problem (it always has complexity $O(n^k)$ if $k$ is less than number of vertices and it has complexity $O(n^n)$ if $k$ is equal to the number of vertices), but I'm not so sure about this.

Is a $k$-clique easier to find if the graph is sparse?

$\endgroup$
  • $\begingroup$ If $k$ is a constant, then there is no sense in asymptotically comparing it to the number of vertices. In any case, if $k$ equals the number of vertices then the question translates to "is the given graph a clique?", which is solvable in linear time, which does not come near $n^n$. $\endgroup$ – Ariel Jan 22 '18 at 18:20
1
$\begingroup$

Given a graph $G$ on $n$ vertices, you can always add $\binom{n}{2}$ new vertices not connected to anything to get a new sparse graph $G'$ with the same clique number. So assuming that the graph is sparse doesn't make it much easier to find its largest clique. In particular, determining whether a sparse graph has a clique of given size (which is part of the input) is NP-complete.

$\endgroup$
  • $\begingroup$ ok so you're basically saying that it doesn't change anything if the graph is G or is G', right? $\endgroup$ – kdpkke Jan 22 '18 at 18:45
  • 1
    $\begingroup$ It changes a lot of things, but not the clique number (i.e., the size of the largest clique). $\endgroup$ – Yuval Filmus Jan 22 '18 at 18:46
  • $\begingroup$ i accept your answer as the best one, thanks! $\endgroup$ – kdpkke Jan 22 '18 at 18:57
2
$\begingroup$

Let me not completely agree with Yuval's answer.

Indeed, in some sense sparsity does make a maximum clique problem easier, and this is proved also by solving it on real-life networks. Usually benchmarks for a maximum clique are pretty dense. And here is why.

  1. If it is known an integer $k$ that is a lower bound of the clique number (or the number itself, but we are looking for a clique), then one can reduce the graph to $(k-1)$-core, that is the graph where each node has a degree at least $k-1$. The resulting graph might be considerably smaller in size and thus, for example, IP solver might get a huge boost. How to reduce: delete all vertices with degree smaller than $k-1$ until those exist.
  2. If you look at sparsity not from the density perspective, but from the degeneracy perspective, things are even more formalized. Usually we say that graph is "sparse" when its degeneracy is low. And there exists FPT algorithms with running time around $O^{*}(2^{d/4})$ where $d$ is graph's degeneracy (here big-O star means that the algorithm depends polynomially on the graph size).

Conclusively, the maximum clique problem is immensely easier on sparse instances, though it still remains $\mathcal{NP}$-Complete (but FPT on degeneracy).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.