# Quasi-Stable Coloring

*Graph compression for performant approximations*

QuasiStableColors.jl is a library for compressing graphs and approximating graph algorithms. The compressed graphs are computed using an algorithm called *quasi-stable coloring*, which results in a much smaller graph while preserving its key properties. We introduce this approach in our research paper "Quasi-stable Coloring for Graph Compression."

A major advantage of this approach is that many algorithms can be computed directly on the compressed graph, *without needing decompression*. This results in an effective approximation of many graph algorithms. Applications implemented in this library are:

- Betweenness centrality
- Maximum-flow/minimum-cut
- Linear optimization

## Publication

The details of this work are available in our paper "Quasi-stable Coloring for Graph Compression." This includes theoretical analysis, the algorithm and experimental results.

If you use this library, we ask that you cite our paper:

```
@article {q-stable-coloring,
title = {Quasi-stable Coloring for Graph Compression: Approximating Max-Flow, Linear Programs, and Centrality},
author = {Moe Kayali and Dan Suciu},
journal = {Proc. VLDB Endow.},
volume = {16},
number = {4},
year = {2022},
}
```

Quasi-stabling coloring was developed within the databases group at the University of Washington, Seattle.

## Resources

**Tutorial**: Start here! Examples and code to get started with using this library.**Reference**: Reference documentation for all the public functions of this library can be found in the API section. Specific sections explain the applications: maximum-flow/minimum-cut problems, betweenness centrality computation and linear optimization.**Researchers' Guide**: Want to extend quasi-stable coloring to a new domain? Perhaps you want to develop a variant of approximate colorings? The Internals section covers these topics.**Questions**? Ask questions and report bugs using Github issues.