ProblemReductions

Warning: This project is under active development.

This repository is for an ongoing project of open source promotion plan (OSPP) 2024: A Julia package for problem reduction between computational hard problems.

This package is expected to be a tool for researchers to study the relationship between different computational hard problems. It defines a set of computational hard problems and provides a set of functions to reduce one problem to another. The package is designed to be extensible, so that users can easily add new reductions to the package.

On the release of the package, it is expected to cover all the problems that are used in GenericTensorNetworks.jl, and will become a dependency of GenericTensorNetworks.jl. The listed problems are:

• (Maximal) Independent Set
• Max-Cut
• Graph Coloring
• Spin Glass
• Set Packing
• Set Covering
• Satifiability problem
• Dominating Set

Developer note

You should have Julia installed on your machine to run the following commands. Please refer to the setup guide for installation.

To initialize the package environment, open a terminal and run the following command in the package directory:

make init   # or use `make update` to update

To run the tests, please type

make test

To serve the documentation locally, please type

make serve