Let $G=(V, E)$ be an undirected graph with vertex set $V$ and edge set $E$. Let $V'=\{v_1, v_2, ..., v_k\}$ be a subset of $V$ where degree of each $v_i$ is bigger than or equal to $k$. Is there a way to check whether $V'$ is a $k$-clique more efficient than the brute-force algorithm in $O(k^2)$? Thanks in advance.

  • 4
    $\begingroup$ It would depend on how the graph $G$ is given as an input (for instance if it's given by its adjacency matrix then $k^2$ is asymptotically optimal, if it's given by an edge clique cover then you can probably do better), it might be best to explicit this in the question (although any reasonable reader would assume it's given as an adjacency matrix or adjacency lists...) $\endgroup$ – integrator Dec 4 '19 at 17:46
  • $\begingroup$ Thanks for asking this. $G$ is given with an edge list. Hence we have the adjacency list of the vertices, not the adjacency matrix. I work on large graphs, hence using the adjacency matrix will be a problem for me. $\endgroup$ – Mehmet Aktas Dec 4 '19 at 19:27
  • $\begingroup$ Can you describe the $O(k^2)$ brute-force you assumed in the question? $\endgroup$ – narek Bojikian Dec 4 '19 at 23:14
  • $\begingroup$ You basically check whether there is an edge between each pair of vertices in $V'$ in $O(k^2)$. $\endgroup$ – Mehmet Aktas Dec 5 '19 at 4:16
  • $\begingroup$ I suppose that this earlier question could be helpful. $\endgroup$ – Juho Dec 5 '19 at 10:58

Your Answer

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

Browse other questions tagged or ask your own question.