The Computational Complexity of 3k-CLIQUE

Title: The Computational Complexity of 3k-CLIQUE

Research Question: What is the minimum time complexity required for a deterministic and exact algorithm to solve the 3k-CLIQUE problem, which involves finding a clique of size 3k in a given undirected graph?

Methodology: The study proposes a method to create an auxiliary graph G′ with O(nk) vertices and O(n2k) edges. The 3-CLIQUE problem on G′ is equivalent to the 3k-CLIQUE problem on the original graph G. The Hadamard product of the adjacency matrix of G′ is used to determine if there is a 3-clique in the graph.

Results: The main result is that the fastest deterministic and exact algorithm that solves the 3k-CLIQUE problem must run in Ω( n2k) time in the worst-case scenario on a classical computer, where n is the number of vertices in the graph. This lower bound is confirmed by the fact that the fastest known deterministic and exact algorithm that solves 3k-CLIQUE was published in 1985 and has a running time of Θ( nωk), where ω ≥ 2.

Implications: This research has significant implications for the field of computational complexity. It sets a lower bound on the time complexity for solving the 3k-CLIQUE problem, which has practical applications in various areas of computer science and mathematics. The results also contribute to our understanding of the limits of deterministic algorithms and the nature of NP-complete problems.

Link to Article: https://arxiv.org/abs/0310060v13 Authors: arXiv ID: 0310060v13