Approximation Algorithms - Vertex Cover Analysis

This repository presents an experimental study of approximation and heuristic algorithms for the Vertex Cover problem, a classical NP-hard problem in graph theory.

The goal of this study is to empirically evaluate how different approximation strategies perform in practice, focusing on the trade-off between solution quality (size of the vertex cover) and runtime efficiency across randomly generated graphs.

---

Problem Statement

Given an undirected graph ( G = (V, E) ), the Vertex Cover problem asks for the smallest subset of vertices such that every edge in the graph is incident to at least one selected vertex.

Since computing the minimum vertex cover is NP-hard, this code compares several approximation and heuristic algorithms that offer practical solutions with reasonable guarantees.

---

Algorithms Evaluated

The following approaches are implemented and analyzed:

• GreedyMIS : Greedy maximal independent set–based approximation
• LP Rounding : Linear programming relaxation followed by rounding
• NeighborCover : Degree-based heuristic
• ParallelNeighborCover : Parallelized variant of the heuristic approach

Each algorithm is evaluated based on:

• Size of the vertex cover produced
• Execution time (runtime)

---

Experimental Setup

• Graphs are generated using the Erdős–Rényi random graph model
• Experiments are conducted across varying:
  • Number of vertices
  • Edge probabilities (graph density)
• For each configuration, all algorithms are run and compared

Metrics Recorded

• Vertex Cover Size
• Runtime
• Aggregated algorithm performance across configurations

All results are stored in CSV format for reproducibility and further analysis.

---

Analysis Methodology

For each graph configuration (number of vertices, edge probability):

• The algorithm producing the smallest vertex cover is recorded
• The algorithm with the fastest runtime is recorded
• Aggregate statistics are computed to identify:
  • Which algorithm most frequently produces smaller solutions
  • Which algorithm is most often the fastest

A summary table is generated and saved for comparison.

---

Repository Structure

• approximation_algorithms.ipynb : Main experimental notebook (implementation + analysis)
• vertex_cover_results.csv : Raw experimental results generated by the notebook
• algorithm_performance_summary.csv : Aggregated performance metrics
• requirements.txt : Python dependencies
• README.md : Project documentation

How to Run

1. Install dependencies:

   pip install -r requirements.txt

2. Open the notebook:

   jupyter notebook notebook/approximation_algorithms.ipynb

3. Run all cells to reproduce experiments and analysis.

Key Takeaways

This study highlights practical trade-offs between solution quality and efficiency when solving NP-hard problems using approximation techniques, and provides empirical insight into when faster heuristics outperform more computationally expensive methods.