Table of Contents
Longest Induced Path
Here, you can find the benchmark sets used in our study of Longest Induced Path (LIP). Details can be found in:
- F. Bökler, M. Chimani, M.H. Wagner, T. Wiedera. Stronger ILP Models for Maximum Induced Path. submitted to ISAAC 2019
Instances
| Type | Description | Filename | Solutions |
|---|---|---|---|
| MG | moviegalaxies | lip_mg.tar.bz2 | results_mg.csv |
| CRN | Real world networks | lip_crn.tar.bz2 | results_crn.csv |
| BAL | Barabasi-Albert graphs with 100 nodes | lip_bal.tar.bz2 | results_bal.csv |
| BAS | Barabasi-Albert graphs with 20-40 nodes | lip_bas.tar.bz2 | results_bas.csv |
File format of the instances
The tar.bz2-files contain plain text files in the graphml format, where each graphml file contains a single instance. The naming scheme for these files is as follows:
Moviegalaxy instances: <movie title>.graphml Realworld instances: <name>.graphml Barabasi-Albert: ba.<#nodes>.<density>.<instance number>.graphml
File format for the solutions
The solution files are plain text files in the CSV format with a comma as the delimiter. The first line of a file serves as a column header. Each further line represents a specific instance. The column headers are as follows:
| Header | Description |
|---|---|
| filename | the filename of the specific instance |
| #n | the number of nodes |
| #m | the number of edges |
| OPT | the optimal solution or -1 if none was found |
| Walk RT | the runtime of ILP_Walk in seconds |
| Walk OPT | the best solution found by ILP_Walk |
| Flow RT | the runtime of ILP_Flow in seconds |
| Flow OPT | the best solution found by ILP_Flow |
| C_[n,c]_(int|frac) RT | the runtime of ILP_Cut in seconds |
| C_[n,c]_(int|frac) OPT | the best solution found by ILP_Cut |
We tested 8 configurations of ILP_Cut. For each there are two columns. The naming scheme of the configurations is the same as in the paper: n indicates that the edge variables are relaxed and node variables are added; c that clique constraints for a heuristically found set of disjoint cliques were added before solving the ILP. int or—otherwise—frac indicate that the separation uses only integral or also fractional solutions, respectively.