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
    Commented Dec 4, 2019 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$ Commented Dec 4, 2019 at 19:27
  • $\begingroup$ Can you describe the $O(k^2)$ brute-force you assumed in the question? $\endgroup$ Commented Dec 4, 2019 at 23:14
  • $\begingroup$ You basically check whether there is an edge between each pair of vertices in $V'$ in $O(k^2)$. $\endgroup$ Commented Dec 5, 2019 at 4:16
  • $\begingroup$ I suppose that this earlier question could be helpful. $\endgroup$
    – Juho
    Commented Dec 5, 2019 at 10:58


Your Answer

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

Browse other questions tagged or ask your own question.