This repository presents an extensive report on the k-clique problem, accompanied by source code for both a brute force algorithm and a heuristic algorithm. The report includes comprehensive testing results for various graph sizes.
The report begins by providing a detailed explanation of the k-clique problem, its theoretical foundations, and its practical applications in real-life scenarios. It offers a proof of its NP-completeness, showcasing its computational complexity.
Furthermore, the report presents a brute force algorithm and a heuristic greedy algorithm, providing thorough explanations of their functioning, pseudocode representations, and an analysis of their time complexity. The brute force algorithm is supported by an inductive proof, while the limitations of the heuristic algorithm are highlighted.
In addition, the report compares and contrasts the two algorithms, emphasizing their respective time and performance considerations. Sample runs are provided for both algorithms, demonstrating their efficacy in limited cases.
The repository also includes driver code for both algorithms, as well as a random graph generator to facilitate testing. Lastly, an experimental analysis for performance testing is conducted using various sample sizes, employing the central limit theorem to compare the performance of the algorithms.
