# Undoing Vertex Cover Data Reduction Rules
  This is an implementation of the the Find, Inflate&Deflate, Find and Reduce, and Local Inflate&Deflate methods.
  A user friendly wrapper script (`shrink_instance.py`) is provided to simplify the task of using these tools to obtain smaller irreducible graphs.

## Requirements
  A C++ compiler and Python 3.
  The included scripts (Bash and Python) have only been tested on a Linux system.

## Compiling
  Run `./compile.sh` to compile all project components.

## File formats
  The programs read a graph described in a simple edge list format from the standard input.
  Each line contains two adjacent vertices.
  Vertex names may use letters and numbers, but no whitespace.
  An example graph called `petersen.txt` is included with this project.
  A comment line always starts with `#`.

# Shrinking instances
  Example usage: `python3 shrink_instance.py --timeout=60 input.txt output.txt`

  See `python3 shrink_instance.py --help` for more parameters.

  The script takes as input an input graph (`input.txt`) and outputs an irreducible graph (`output.txt`).
  A timeout may be specified using `--timeout`, otherwise a default timeout is used.

  The script has two main phases: "presolving" and "undo-based shrinking".

## Presolving phase
  In the presolving phase data reduction rules are applied to the input.
  There are four presolve modes: `light, medium, medium+, heavy` which are ordered by increasing computational effort.

  Some frequently occurring sequences of forward and backward rules which shrink graphs have been directly implemented as new rules (guided rules).
  All modes except light use these new "guided" rules.

  Use `--presolve=<mode>` to set the presolve mode.
  
## Undo-based shrinking phase
  In this phase forward rules (i.e. data reduction rules) and backward rules are applied so that the graph becomes smaller.


  There are three modes: `FAR, ID, mixed`. The mixed mode uses both FAR and ID modes. FAR finds short sequences of forward and backward rules which shrink the graph, whereas ID randomly applies forward and backward rules; first in an inflate then deflate phase.

  Use `--mode=<mode>` to set the mode for this phase.

  * `--ID=pct` - tells ID to inflate the graph by pct percent during the inflate phase
  * `--FAR=d` - tells FAR to find sequences of forward and backward rules of length at most d


# Solution recovery
  The output file created by `shrink_instance.py` contains comments with instructions on how to recover a solution for the original instance from a solution to the kernel.
  The included script `recovery.py` takes care of this recovery process.

  Usage: `python3 recovery.py kernel.txt kernel.solution original.txt`
  * kernel.txt - the smaller instance / kernel computed by `shrink_instance.py`
  * kernel.solution - a file containing a vertex cover for the kernel - each line of the file is the name of a vertex included in the solution
  * original.txt - the graph passed to `shrink_instance.py` from which `kernel.txt` was computed

  The last argument (original.txt) may be skipped, however this omits a verification step that ensures that the recovered solution is a valid vertex cover.

# Included Vertex Cover solver
  In `solver/` we provide an implementation of a Vertex Cover solver which incorporates a wide range data reduction rules, including new data reduction rules: Guided Struction, Guided Magnet, Guided Unconfined, which correspond to specific types of forward and backward rule sequences.

  This solver uses a branch-and-reduce paradigm similar to the solver of Akiba and Iwata [TCS'16].
 
  Example usage: `./solver/main --rrules=[deg1,deg2,unconf] < input.txt > solution.txt`
  
  Run with `--help` to get a list of all options.
  Which data reduction rules to use can be specified with , e.g., `--rrules=[deg1,deg2,unconf,lp]`.
  The square brackets around a list of rules tell the solver to apply them exhaustively.
  If the square brackets are not used, then the rules are applied in a single pass.
  For a full list of data reduction rule names see `str_to_rr()` in `solver/config.cpp`.

  Note that, e.g., `undeg2, undeg3, uncn, oe_densify` are backward rules, and should only be used with caution so as to not increase the graph size too much.

# Advanced usage - rrfinder
  The rrfinder program is a specialized tool for controlled application of forward and backward rules.
  The goal of this tool is to automate the process of applying forward and backward rules to shrink an already irreducible graph, and to find sequences of rules that achieve this.

  While many of the rules implemented in `rrfinder` and also implemented in `solver`, the latter focuses on being able to quickly apply these rules exhaustively, thus giving up some control.

## Usage:
  The basic usage is as follows
  `./rrfinder/main < petersen.txt > output.txt`


## Basic options
  using `--mode=MODE` where MODE is any of `FIND,FAR,ID,LID` one may choose which method of applying forward and backward rules to use.
 * `FIND` - invokes the Find Method
 * `FAR` - invokes the Find and Reduce Method
 * `ID` - invokes the Inflate&Deflate Method
 * `LID` - invokes the Local Inflate&Deflate Method

 * `--check-isomorph` - turns on local isomorphism testing in the `FIND` method
 * `--branch-depth=d` - tells `FIND` and `FAR` to consider sequences of at most d forward and backward rules
 * `--max-inflate=pct` - tells `ID` and `LID` what inflation ratio to use

### Advanced options
  See `--help` for a few more options.
  Some configuration parameters are hard-coded in `rrfinder/config.h` and not exposed to the user.

### Visualization
  NOTE: the option `--print-graph-mod` needs to be used for the relevant graph modification data to be output.

  Using `python3 rrfinder/viz.py output.txt` on the output of the `FIND` or `FAR` methods one may inspect the graph modifications corresponding to the sequence found by the method.

  Software prerequisites:
 * python3 libraries: matplotlib, numpy, networkx, netgraph