Weighted F-free Edge Editing

Example of a protein-protein interaction network which is edited to be (C4, P4)-free. The connected components can be interpreted as clusters of the original graph.

This is the source code for a bachelor thesis regarding the Weighted F-free Edge Editing Problem [PDF]. We implement exact FPT and ILP algorithms. The FPT algorithm is based on work from [GHS+20] for (unweighted) F-free Edge Editing.

The code was further developed after the thesis was submitted. The project state at the time of submission can be found in commit fa537279.

Setup and Installation

Dependencies

The required dependencies are Boost, YAML CPP and robin-hood-hashing. To clone submodules and install the dependencies execute the following commands:

git submodule update --init --recursive
sudo apt install libboost-all-dev libyaml-cpp-dev

Optional Dependencies

Gurobi is a commercial LP-Solver. It is used for an ILP algorithm as an alternative solver and for Linear Program Relaxation to compute lower bounds for the FPT algorithm. You can get Gurobi here.

nps_mwis is a Maximum Weight Independet Set (MWIS) solver from [NPS18] (website). It is used for computing a subgraph packing to get lower bounds for the FPT algorithm. It can be downloaded by executing extern/nps_mwis/get.sh.

lsswz_mwis is also a MWIS solver used for lower bounds. It is from [LSSWZ18] and the code is not publicly available.

Datasets

The datasets used are protein-protein interaction matrices derived from the biological dataset. The instances must follow the METIS data format for graphs. The datasets can be downloaded and transformed using snakemake.

snakemake -j all \
    data/bio \
    data/bio-C4P4-subset \
    data/bio-subset-A \
    data/bio-subset-B \
    data/bio-unweighted

Alternatively, the required scripts can be executed by hand.

python3 scripts/download_dataset.py --dir data/bio --config data/bio.yaml --biological --max-size 1000
python3 scripts/generate_dataset_subset.py data/bio-C4P4-subset.yaml
...

Building

The project uses CMake for building.

mkdir build && cd build
cmake .. -DCMAKE_BUILD_TYPE=Release
make fpt

To try out the algorithm you can use this example.

build/fpt --multiplier 100 --F C4P4 \
    --input data/bio/bio-nr-3-size-16.graph \
    --lower-bound SortedGreedy \
    --selector MostAdjacentSubgraphs \
    --search-strategy Fixed --k 500

How to cite

Jonas Spinner. Weighted F-free Edge Editing. Bachelor thesis, Karlsruhe, 2019.

@thesis{Spinner2019,
    author       = {Spinner, Jonas},
    year         = {2019},
    title        = {Weighted F-free Edge Editing},
    doi          = {10.5445/IR/1000135117},
    publisher    = {{Karlsruhe Institute of Technology (KIT)}},
    pagetotal    = {53},
    type         = {Bachelor thesis},
    school       = {Karlsruhe Institute of Technology (KIT)},
    language     = {english}
}

License

This project is licensed under the MIT license. The licenses of external sources can be found in their respective directories.