McSplit+DSB

A new upper bound computation for the branch-and-bound (BnB) algorithm, McSplit, designed to solve the maximum common induced subgraph (MCIS) problem. We call it as the McSplit+DSB (Degree Sequence Bound).

Prerequisites

• C++ compiler
• Make (optional)

Build and Test

Linux

Use the following command to build this program in Linux operating system.

$ mkdir bin
$ make build

MacOS

Use the following command to build this program in macOS.

$ mkdir bin
$ make macbuild

Testing the Program

$ make test

Expected output.

$ make test
./bin/run.o min_max ./data/tests/case1/pattern ./data/tests/case1/target -l -q -t 100
6, 1, 1.9792e-05, 2.7542e-05, 28, 6, 20, 0
./bin/run.o min_max ./data/tests/case2/pattern ./data/tests/case2/target -l -q -t 100
6, 1, 1.2291e-05, 1.5833e-05, 21, 6, 15, 0
./bin/run.o min_max ./data/tests/case3/pattern ./data/tests/case3/target -l -q -t 100
7, 1, 1.2542e-05, 2.8958e-05, 76, 21, 52, 0

The output displays comma-separated values for the following attributes:

1. Size of the maximum induced common subgraph.
2. Returns (1) if the common sub-graphs are isomorphic, (0) otherwise.
3. Time in seconds to find the optimal solution.
4. Time in seconds to verify the optimality by completing the search.
5. Number of recursive calls (branches) made to complete the search.
6. Number of recursive calls (branches) made to find the optimal solution.
7. Returns (1) if the search is terminated prematurely, (0) if the search is fully completed.

Apply Proposed Bound to RL Extensions

Follow the steps in this doc.