Repository files navigation

Maximum Independent Set Problem Analysis and Implementation

Welcome to the MIS-Project repository! This project focuses on analyzing and implementing solutions for theMaximum Independent Set (MIS) Problem, a classic NP-complete problem in graph theory. The repository includes both abrute-force and aheuristic algorithm to solve the MIS problem, along with comprehensive experimental analysis.

TheMaximum Independent Set Problem (MIS) involves finding the largest set of mutually non-adjacent vertices in a given graph. This project addresses both thedecision problem and theoptimization problem for MIS using two different algorithms:

1. Brute-Force Algorithm: Guarantees an optimal solution by exploring all possible subsets.
2. Heuristic Algorithm: Provides a near-optimal solution with improved computational efficiency.

• Communication Systems: Minimizing interference by selecting non-adjacent network nodes.
• Task Scheduling: Scheduling non-overlapping tasks.
• Social Networks: Identifying non-connected groups in social networks.

• Brute-force algorithm with correctness and quality analysis.
• Heuristic algorithm with performance testing and accuracy evaluation.
• Random instance generator for testing on various graph sizes and densities.
• Graph visualizations to illustrate algorithm outputs.
• Comparison of results between brute-force and heuristic approaches.

• Thebrute-force algorithm was tested on small graphs and provided exact solutions.
• Theheuristic algorithm achieved anaverage accuracy of 96%, with consistent results across varying graph sizes.
• Extensive testing included2,500 instances of randomly generated graphs to validate performance and accuracy.

📂 MIS-Project
├── 📂 6 # Section 6 test results (CSV)
├── 📂 7 # Final changes for Section 7
├── 📂 8 # Section 8 test results
├── 📂 plots # Graph plots for heuristic tests
├── 📂 samples # Generated sample graphs
├── .gitignore # Git ignore file
├── LICENSE # MIT License
├── README.md # Project readme file
├── bruteForce.py # Brute-force algorithm implementation
├── heuristic.py # Heuristic algorithm implementation
├── heuristicvisual.py # Visualization script for heuristic tests
├── main.py # Main script for running the algorithms
├── results.csv # CSV file containing test results
├── sampleGen.py # Random instance generator
├── section6Analysis.ipynb # Jupyter Notebook for Section 6 analysis
├── section6Samples.py # Section 6 sample generation script
├── section6Tests.py # Section 6 test script
├── section7Analysis.ipynb # Jupyter Notebook for Section 7 analysis
├── section7Samples.py # Section 7 sample generation script
├── section7Tests.py # Section 7 test script
├── section8Samples.py # Section 8 sample generation script
├── section8Tests.py # Section 8 test script
├── stats.py # Statistical analysis script
├── testGen.py # Test generation script
├── testinfo.txt # Information on heuristic test samples
├── verify.py # Heuristic validation script
└── visualize.py # Graph visualization functions

• Ali Khaled A. Ishtay Altamimi
• Nuh Al-Sharafi

This repository is licensed under the MIT License. See the LICENSE file for more details.

For questions or feedback, feel free to reach out:

• Ali Khaled A. Ishtay Altamimi:ali.altamimi@sabanciuniv.edu
• Nuh Al-Sharafi:nuh.sharafi@sabanciuniv.edu