CSE6140-Project: Minimum Vertex Cover

Rao Fu, Huizi Shao, Shangru Yi, Zhe Zhou

Team project repo for CSE6140 (FALL 2020) in Georgia Institution of Technology

The Minimum Vertex Cover (MVC) problem is a typical NP-complete problem that plays a significant role in many practical applications such as operation research, network security, computational biology and parallel machine scheduling. In this project, four algorithms, i.e. Branch-and-Bound (BnB), Max Degree Greedy Approximation, Two Weighting Local Search (Cai, Shaowei, etc. AAAI'15), Simulated Annealing Local Search are implemented to obtain the minimum vertex cover (MVC). A dummy solution using NetworkX is also included in this project for reference. Please refer to /doc/ProjectDescription.pdf and /doc/11.pdf for project details.

Install Python Dependencies for Local Running

This project use Python 3+ (3.7.4 for implementation). We recommend to use python virtual environment to avoid possible dependency conflicts.

Following shell snippet can be used to create a local virtual environment.

For windows:
  cmd cd to current directory (../CSE6140-Project/)
  
  python3 -m venv env
  env\Scripts\activate.bat  # activate virtual environment
  pip install -r dependencies.txt

For linux / MacOS:
  terminal cd to current directory (../CSE6140-Project/)
  
  python3 -m venv env
  source env/bin/activate  # activate virtual environment
  pip install -r dependencies.txt

After the virtual environment is created and activated, use following command to run scripts.

python main.py -inst <filePath> -alg [BnB|Approx|LS1|LS2] -time <cutoff in seconds> -seed <random seed>
# see more usage with -h (batch run, experiment repeat, solution completeness check, etc. 
# filePath example (relative path): ./data/Data/dummy1.graph

If you install new package to the environment, make sure you update dependencies.txt with correct package name and version, and commit. Just add the main package with version to dependencies.txt should be fine. Refer to dependencies.txt for example dependencies.

Following shell snippet can be used to retrieve installed package lists.

pip freeze  # get current installed packages and version info

Paper Reference Lists

Branch and Bound

An Exact Algorithm for Minimum Vertex Cover Problem paper link

Local Search

Two Weighting Local Search for Minimum Vertex Cover (AAAI 2015) paper link
Local search with edge weighting and configuration checking heuristics for minimum vertex cover Cover (revised from AAAI 2010, Artificial Intelligence) paper link
An efficient simulated annealing algorithm for the minimum vertex cover problem paper link

Approximation

Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms (Theortical Computer Science) paper link
Analytical and Experimental Comparison of Six Algorithms for the Vertex Cover Problem paper link
NMVSA Greedy Solution for Vertex Cover Problem paper link
Analytical and experimental comparison of six algorithms for the vertex cover problem paper link
An Approximation Algorithm for the Minimum Vertex Cover Problem paper link

Python NetworkX

Bar-Yehuda, R., and Even, S. (1985). "A local-ratio theorem for approximating the weighted vertex cover problem."Annals of Discrete Mathematics, 25, 27–46, MVC Sol

yishangru/CSE6140-Project