NAC-colorings search: complexity and algorithms

Flexible realizations existence: NP-completeness on sparse graphs and algorithms

Petr Laštovička and Jan Legerský

In this repository, we provide our code for the NAC-coloring search algorithm described in a bachelor thesis and in our paper. We prepared a notebook NAC_playground.ipynb where you can experiment with the algorithm and NAC_presentation.ipynb in which you can see how we run and analyze benchmarks. You can also run them yourself. To understand interface overview more in detail, we recommend reading chapter Implementation in the thesis.

Setup

Python 3.12 or higher is required.

python -m venv .venv
source .venv/bin/activate
pip install -r requirements.txt

Tests

You can run tests by executing pytest. The packages also contains base for Cartesian NAC-coloring search, the related tests are skipped for now as it is not yet fully implemented for every approach.

Structure

• nac - the implementation of our NAC-coloring related algorithms and heuristics
• stablecut - the implementation of an algorithm to search for stable cuts
• benchmarks - utility files related to benchmarks - graphs loading, generation, analysis notebook utility functions
• benchmarks/precomputed - Results of the benchmarks as run on our hardware
• graphs_store - stores generated graphs of selected classes

For complete and more exhaustive documentation, see the code.

Graphs dataset

We list sources of the graph classes and generation tools used to create graph datasets of specific graph classes. Benchmarks later use these graphs to perform algorithms comparison. All the graphs are stored in the graphs_store directory. For proper description, see the thesis.

Minimally rigid graphs

We listed all minimally rigid graphs using Nauty with nauty-laman-plugin.

We swiftly describe the folder contents: ./nauty/minimally_rigid_all holds all the minimally rigid graphs with the given number of vertices (up to 12 vertices).

For benchmarks, minimally rigid graphs were generated randomly as Nauty generates graphs that are quite similar - this is problem for larger graph sizes where if we want to have diverse dataset, it becomes faster to find random graphs than generate them using Nauty. Random minimally rigid graphs are stored in the ./random/minimally_rigid folder.

No 3 nor 4 cycles

The class of graphs that have no 3 nor 4 cycles was obtained from users.cecs.anu.edu.au (external).

For previous testing we also used some graph classes from users.cecs.anu.edu.au. Unfortunately these were not as interesting as not large enough graphs were available.

Globally rigid graphs

Globally rigid graphs were generated by generating random graphs that have no or just few NAC-colorings and checking if they are rigid.

Graphs with no NAC-coloring

These were generated randomly and only graphs with significant number of triangle connected components were kept (we did not find graphs with more monochromatic classes).

License

The code is licensed under MIT license.