Maximum Clique Project

This project studies the Maximum Clique problem from both theory and practice. It includes:

• a full written report (Report.pdf) with proofs, reductions, and complexity analysis,
• a Jupyter notebook (script.ipynb) with multiple clique algorithms and empirical comparisons.

Project Scope

The work covers three layers:

1. Complexity Theory

   • Formal definition of clique decision/optimization versions
   • Distinction between maximum and maximal clique
   • NP-completeness proof of CLIQUE via reduction from 3-SAT
   • Reduction between Independent Set and Clique

2. Exact and Heuristic Algorithms

   • Recursive decision solver for k-clique (HasClique)
   • Brute-force maximum clique search
   • Binary-search-based optimization over clique size
   • Greedy clique heuristic (lower bound)
   • Bron-Kerbosch (basic)
   • Bron-Kerbosch with pivot
   • Tomita pivot strategy (optimized pivot choice)
   • Hybrid approach: Greedy + k-core pruning + Tomita

3. Optimization & Hardness Perspective

   • ILP formulation correctness proof (for Independent Set formulation in the report)
   • LP relaxation upper-bound proof
   • Geometric hardness viewpoint using the Overlap Gap Property (OGP) in random graphs

Repository Structure

• Report.pdf — Main report with definitions, proofs, reductions, and theory narrative
• script.ipynb — Implementations, benchmark code, plots, and validation checks
• LICENSE

What the Notebook Implements

script.ipynb contains:

• random graph generation (Erdős–Rényi style, configurable density),
• recursive clique decision helper,
• Graph class with:
  • brute-force max clique,
  • binary search over clique size,
  • greedy clique heuristic,
  • k-core pruning,
• TomitaGraph class with:
  • Tomita algorithm,
  • Bron-Kerbosch (simple and pivot variants),
  • pruning-augmented exact search,
• runtime measurement utilities,
• comparison plots across graph size and density,
• correctness validation showing agreement across exact methods.

Experimental Setup (Notebook)

The experiments in script.ipynb benchmark algorithms across:

• vertex counts up to around 50,
• multiple graph densities,
• repeated runs with averaging,
• log-scale runtime visualizations.

The notebook includes:

• line plots (runtime vs. graph size),
• bar chart comparisons,
• density-wise grouped comparisons,
• heatmap view of algorithm performance.

Key Theoretical Highlights from the Report

• CLIQUE decision is shown in NP and NP-hard (thus NP-complete).
• A clean reduction from Independent Set to Clique is presented through graph complementation.
• Decision and optimization formulations are shown to be polynomially inter-reducible.
• Complexity discussions include:
  • recursive decision brute-force behavior,
  • Bron-Kerbosch variants,
  • Tomita-style pivoting,
  • practical speedups through core pruning.
• Later sections explain why random-graph instances remain hard through OGP: near-optimal solutions are structurally fragmented, limiting pruning effectiveness.

How to Run

1. Open script.ipynb in Jupyter (VS Code or Jupyter Lab).
2. Ensure Python packages are available:
   • numpy
   • matplotlib
3. Run cells top-to-bottom to reproduce:
   • algorithm implementations,
   • timing benchmarks,
   • comparison figures,
   • validation outputs.

Notes

• The report is the primary source for formal proofs and complexity arguments.
• The notebook is the executable companion for empirical analysis and visualization.
• Exact methods should agree on clique size; greedy is used as a fast approximation / lower bound.