Maximum Clique Algorithms for Disk Intersection Graphs

This repository provides a collection of algorithms implemented in C++ and Python to solve the Maximum Clique problem on Disk Intersection Graphs. It includes exact algorithms, an approximation scheme, and visualization tools to compare their performance and results.

The Problem: Maximum Clique on Disk Intersection Graphs

Disk Intersection Graph

A Disk Intersection Graph is a graph where each node corresponds to a disk in a 2D plane. An edge exists between two nodes if their corresponding disks intersect (i.e., the distance between their centers is less than or equal to the sum of their radii).

Maximum Clique Problem

The Maximum Clique Problem is the problem of finding the largest subset of vertices (nodes) in a graph such that every two distinct vertices in the subset are adjacent. This subset is called the maximum clique. This problem is known to be NP-hard, meaning that no known algorithm can solve it in polynomial time for all graphs.

Algorithms Implemented

This repository explores several algorithms to find the maximum clique:

1. Brute Force: This algorithm checks every possible subset of nodes in the graph to determine if it's a clique. It is guaranteed to find the maximum clique but is very slow, with a time complexity of O(2^n * n^2), making it impractical for all but the smallest graphs.

2. Bron-Kerbosch Algorithm: A recursive algorithm for finding all maximal cliques in a graph. This implementation is adapted to find the single largest clique (the maximum clique).

   • Without Pivot: The basic version of the algorithm.
   • With Pivot: An optimized version that uses a "pivot" element to reduce the number of recursive calls, often resulting in a significant speedup.

3. Branch and Bound: A smarter search algorithm that systematically explores the search space. It keeps track of the largest clique found so far and "prunes" branches of the search that cannot possibly contain a larger clique, making it more efficient than brute force.

4. EPTAS (Efficient Polynomial-Time Approximation Scheme): Since finding the exact maximum clique is computationally expensive, approximation algorithms are often used. An EPTAS finds a clique whose size is at least (1 - ε) times the size of the maximum clique, where ε is a small, user-defined error parameter. The runtime is polynomial for a fixed ε.

Repository Structure

The repository is organized into directories, each containing a specific algorithm or tool:

.
├── branch_and_bound/
│   ├── main.cpp         # C++ implementation of Branch and Bound
│   ├── main.exe         # Compiled executable
│   ├── graph_data.txt   # Output file with graph and clique data
│   └── visua.py         # Python script to visualize the result
├── bron_kerbosch_withoutpivot/
│   └── ... (similar structure)
├── bron_kerbosch_withpivot/
│   └── ... (similar structure)
├── brute/
│   └── ... (similar structure)
├── eptas/
│   └── ... (similar structure)
├── compare/
│   └── visua.py         # Python script to compare all algorithms
└── README.md

• main.cpp: The C++ source code for the algorithm. It generates a random disk graph and finds the maximum clique.
• main.exe: The compiled Windows executable. On other systems, you will need to compile main.cpp.
• graph_data.txt: A file generated by main.cpp that stores the disk properties, graph edges, and the found maximum clique.
• visua.py: A Python script that reads graph_data.txt and visualizes the disk graph, highlighting the nodes of the maximum clique.
• compare/visua.py: A powerful Python script that implements all the algorithms, runs them on a series of random graphs, and generates plots to compare their runtimes and clique sizes.

How to Use

Dependencies

To run the code in this repository, you will need:

• A C++ Compiler: Such as G++ (for Linux/macOS) or MinGW (for Windows).
• Python 3: With the following libraries:
  • matplotlib
  • networkx

You can install the Python libraries using pip:

pip install matplotlib networkx

Running a Single Algorithm

1. Navigate to an algorithm's directory:

   cd brute/

2. Compile the C++ code (if you are not on Windows or want to recompile):

   g++ main.cpp -o main

3. Run the executable:

   ./main  # On Linux/macOS
   main.exe # On Windows

   The program will ask for the number of disks to generate. It will then create/update graph_data.txt with the results.

4. Visualize the result:

   python visua.py

   This will open a plot showing the disk intersection graph and the maximum clique found by the algorithm.

Comparing All Algorithms

The compare/visua.py script allows you to benchmark the performance of all the implemented algorithms.

1. Navigate to the compare directory:

   cd compare/

2. Run the Python script:

   python visua.py

This script will run many test cases with random graphs and then generate and display several plots comparing the average clique sizes, runtimes, and the distribution of these metrics for each algorithm. This is the best way to understand the trade-offs between the different approaches.