Home

Welcome to MaxCliqueApproximator repo!

The max clique problem is the computational problem of finding the maximum complete subgraph inside a randomly generated graph of n nodes. A complete graph is a graph where all nodes are connected to each-other. This problem is an NP-complete problem which is why approximation is needed. Algorithms used to actually solve this problem have extremely high run times when the graph contains 1000+ nodes.

The approximation algorithm works by dividing the graph into subgraphs of a size that we specify. Then we run an isClique method on those subgraphs. We can keep dividing the subgraphs into larger and larger groups while also checking if each group is a clique. What makes this a rough approximation is the randomness involved with dividing the graph into subgraphs. Sometimes the division may not produce subgraphs that are cliques. However, there still could be a clique in the graph. To counter this, we run the division process on the same graph until we reach a clique of a certain size. Then we can repeat the process with larger subgraphs until it takes too long to even reach an answer. This can give us an approximation of the largest clique in the graph.

Real-world applications of this problem arise in large social networks where each person is represented by a node in the graph. Edges connecting two nodes represents people who know each-other and are friends on the social media website. In this case, a clique would represent a group of people who all know each-other.