Experiments: ‘A dynamic programming algorithm for a maximum \(s\)-clique set on trees’

Authors: José Alberto Fernández-Zepeda, Alejandro Flores-Lamas, Matthew Hague, Joel Antonio Trejo-Sánchez.

Description

Experiments in the article “A dynamic programming algorithm for a maximum \(s\)-clique set on trees” were done using RP_2022_Tool (artifact) and the files in this database.

Using the RP_2022_Tool

There’s no installation procedure for the RP_2022_Tool, please download the project and install the packages listed in the Software Dependencies section of the artifact web page.

Input format

RP_2022_Tool accepts Graph Modeling Language¹ (GML) files as input; however, it can be easily modified to support other input files by changing the file /RP_2022_Tool/RP_2022_Tool/src/Utils/input_handler.py.

Configuration files

RP_2022_Tool uses YAML as a configuration file. Configuration files are stored in /RP_2022_Tool/Settings

Experiments

Follow these steps to evaluate the cases of studies mentioned in Section 6 of the paper submitted to the 16th International Conference on Reachability Problems.

1. Download the GML files from the database wep page
2. Unzip the file and place the unziped folder in the location: /RP_2022_Tool/Input
3. Open a command-line interpreter and navigate to the ‘RP_2022_Tool’ folder

   • Type the following command:

         $ python main.py Settings/<case_of_study_config_file>.yaml

   • where <case_of_study_config_file> takes any of the folowing names: T_22_16, T_B, T_D, T_eta, T_L, T_Ph.

Notes

On the output files:

• Results of the execution of the RP_2022_Tool will be placed in the folder /RP_2022_Tool/Output/

On the execution of \(T_{\eta\mathrm{e}{6}}\):

• Experimentation on this case of study will require several hours; please modify the file /RP_2022_Tool/Settings/T_eta.yaml or remove graphs as needed from the \(T_{\eta\mathrm{e}{6}}\) (T_eta.zip file) case of study to suit your needs; in particular, you will need:

  1. Proceed as in the steps 1 and 2 from the Experiments section
  2. In the file /RP_2022_Tool/Settings/T_eta.yaml
     • On line 36 diameters: [] add the values of \(k\) that you want to test; for example, diameters: [10, 100, 500]
  3. Proceed as in step 3 from the Experiments