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 on a classical computer?

Methodology: The study uses an auxiliary graph technique to reduce the 3k-CLIQUE problem to the 3-CLIQUE problem, which is then solved using existing algorithms. The time complexity of these algorithms is then used to derive the lower bound for the 3k-CLIQUE problem.

Results: The research finds 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.

Implications: This result implies that the problem of finding a clique of size 3k in a graph is computationally hard, as it requires at least Ω(n2k) time in the worst-case scenario. This lower bound is confirmed by the fact that the fastest known deterministic and exact algorithm that solves 3k-CLIQUE has a running time of Θ(nωk), where ω ≥ 2.

Significance: This research contributes to the understanding of the computational complexity of graph problems and provides a lower bound for the 3k-CLIQUE problem, which is useful for comparing the efficiency of different algorithms.

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