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?

Improve this question
$\endgroup$
2
  • $\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, 2018 at 18:20
  • $\begingroup$ I would say that this question would be better if the sparsity definition was strengthened to say that every subgraph $G'$ has $|E(G')| \leq c \cdot |V(G')|$ for some constant $c \ll n$. This would remove the trivial case where you can simply add $n^2$ isolated vertices, and it would also give a positive answer. $\endgroup$
    – Pål GD
    Nov 16, 2022 at 11:25

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
3
  • $\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, 2018 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, 2018 at 18:46
  • $\begingroup$ i accept your answer as the best one, thanks! $\endgroup$
    – kdpkke
    Jan 22, 2018 at 18:57
3
$\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).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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