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 uses a mathematical approach to prove a lower bound on the time complexity of solving the 3k-CLIQUE problem. It introduces an auxiliary graph G′ and shows that determining whether the Hadamard product of two matrices representing G′ equals zero is equivalent to solving the 3k-CLIQUE problem on the original graph G. This implies that any deterministic and exact algorithm must take at least Ω( n2k) time in the worst-case scenario, where n is the number of vertices in the graph.

Results: The main result of the study is the lower bound of Ω( n2k) on the time complexity of deterministic and exact algorithms for solving the 3k-CLIQUE problem. This bound is confirmed by the fact that the fastest known deterministic and exact algorithm, published in 1985, has a running time of Θ( nωk), where ω≥2.

Implications: The lower bound on the time complexity has implications for the complexity of the 3k-CLIQUE problem and the algorithms used to solve it. It suggests that there may be limitations in the efficiency of deterministic and exact algorithms for solving this problem, and it may motivate research into alternative approaches, such as probabilistic algorithms or approximation algorithms.

In conclusion, the study provides a lower bound on the time complexity of deterministic and exact algorithms for solving the 3k-CLIQUE problem, which is equivalent to finding a clique of size 3k in a given undirected graph. The results imply that there may be limitations in the efficiency of current algorithms, which could motivate further research into alternative approaches.

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