Minimum-vertex-cover

Comparison of algorithms (exact and heuristic) for the minimum vertex cover problem

Documentation can be found here

Usage

Run

To run the algorithms, you can either use cargo or use run.sh script.

sh run.sh [-c] <algorithm> <file_name> <time_limit> 

• -c : If you want to run the algorithm on the complement of the graph.
• <algorithm> : The algorithm you want to run. It can be bnb, numvc or naive_search.
• <file_name> : The name of the file in the resources/graphs folder.
• <time_limit> : The time limit in seconds.

Algorithms

Exact algorithms

• Naive method : iterate over all possible subsets of vertices and check if it is a vertex cover.
  use : cargo run -r --bin naive_search <file_name> <time_limit>
• Branch and bound : Algorithm based on the paper presented by Wang et al. Source
  use : cargo run -r --bin bnb <file_name> <time_limit> [-c]

Heuristic algorithms

• NuMVC : Algorithm proposed by Cai et al. in their paper : NuMVC: An Efficient Algorithm for the Minimum Vertex Cover Problem. You can find the paper here
  use :cargo run -r --bin numvc <file_name> <time_limit> [-c]
• SAMVC : Algorithm based on the simulated annealing algorithm.
  use : cargo run -r --bin samvc <file_name> <time_limit> [-c]

Bins

• naive_method: Find the MVC of the graph using the naive method.
  use : cargo run -r --bin naive_search <file_name>
• add_graph_to_yaml: Update the graph information in the yaml file (get the graphs in the resources/graphs folder)
  use : cargo run -r --bin add_graph_to_yaml
• bnb: Find the MVC of the graph (or the complement if -c is added) using the branch and bound algorithm.
  use : cargo run -r --bin bnb <file_name> [-c]
• clique: Find the value of the maximum clique of the graph by find the MVC of the complement using the BnB algorithm.
  use : cargo run -r --bin clique <file_name>
• numvc: Find the MVC of the graph (or the complement if -c is added) using the NuMVC algorithm.
  use: cargo run -r --bin numvc <file_name> <time_limit> [-c]
• samvc: Find the MVC of the graph (or the complement if -c is added) using the Simulated Annealing algorithm.
  use: cargo run -r --bin samvc <file_name> <time_limit> [-c]