Raw File
Tip revision: e1ae11cc7393fb43593b717ec7d5ab3b3a08d6a0 authored by Aleskander Figiel on 29 June 2023, 17:41:26 UTC
Fix mistake in README
Tip revision: e1ae11c
# Software prerequisites:
 A C++ compiler such as g++ and a Gurobi installation

# Compilation
  Run `make` in the `degeneracy/` directory

  Modify the `GUROBI` variable in `max_subgraph/Makefile`to point at Gurobi installation on your system

  Run `make` in the `max_subgraph/` directory

# Graph file format
  The graphs use a simple edge list format. Each line of the input contains the names of the vertices of the edge separated by a space.

# Usage:
## Generalized degeneracy
  The executable `degeneracy/gen_degeneracy` computes a generalized degeneracy odering of the input graph (via standard input)

  The following computes the 2-weak-degeneracy of the example greaph

  `./degeneracy/gen_degeneracy --type=weak --x=2 < example_graph.txt`

  The following computes the 2-strong-degeneracy of the example greaph

  `./degeneracy/gen_degeneracy --type=strong --x=2 < example_graph.txt`

## s-Plex and s-Club solvers
  The executable `max_subgraph/max_subgraph` computes the maximum s-Plex or s-Club of an input graph (file as argument) given some ordering of the vertices .


  Generate necessary orderings:

  `./degeneracy/gen_degeneracy --type=weak --x=2 < example_graph.txt > example_2wdg_ordering.txt`

  `./degeneracy/gen_degeneracy --type=weak --x=3 < example_graph.txt > example_3wdg_ordering.txt`

  Compute maximum 2-club using turing kernelization:

  `./max_subgraph/max_subgraph --solver=2club --x=2 example_graph.txt example_2wdg_ordering.txt`

  Compute maximum 3-club using turing kernelization:

  `./max_subgraph/max_subgraph --solver=3club --x=3 example_graph.txt example_3wdg_ordering.txt`

  Compute maximum conncted 2-plex using turing kernelization:

  `./max_subgraph/max_subgraph --solver=splex --splex=2 --x=2 example_graph.txt example_2wdg_ordering.txt`

  Additional options
  * --lb=integer - provide a lower bound on the solution size
  * --no-imrovement-constraint - do not add lower bound constraints to the ILPs
  * --no-turing-kernel - turn off turing kernelization

# Dataset
  In our experiments the dataset from was used. The full list of instances used is in `instances.txt`
back to top