Does the k-clique problem became easier on sparse graphs?
-
05-11-2019 - |
سؤال
Some definitions, just to not create confusion:
A sparse graph is a graph that contains a number of edges less or equal than the number of vertices.
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?
لا يوجد حل صحيح
لا تنتمي إلى cs.stackexchange