$k$-Local Graphs

This repository contains the code accompanying the paper:

Christian Beth*, Pamela Fleischmann*, Annika Huch, Daniyal Kazempour, Peer Kröger, Andrea Kulow, and Matthias Renz. $k$-Local Graphs. In Proceedings of Descriptional Complexity of Formal Systems (DCFS), pp. 34–49. Springer Nature Switzerland, 2025.

*Corresponding authors: Christian Beth (implementation), Pamela Fleischmann (theoretical aspects).
The paper can be found here.

$k$-locality is a structural complexity measure for coloured graphs. Given a coloured graph, it determines an enumeration of the colours such that colouring the graph stepwise leads to as few connected components as possible. This repository provides a priority search algorithm to compute the $k$-locality of a graph, which is orders of magnitude faster than exhaustive search.

Citation

If you use this code in your work, please cite the accompanying paper. If you use the code specifically, please also cite the software release.

@InProceedings{10.1007/978-3-031-97100-6_3,
  author    = {Beth, Christian and Fleischmann, Pamela and Huch, Annika
               and Kazempour, Daniyal and Kr{\"o}ger, Peer
               and Kulow, Andrea and Renz, Matthias},
  editor    = {Malcher, Andreas and Prigioniero, Luca},
  title     = {k-Local Graphs},
  booktitle = {Descriptional Complexity of Formal Systems},
  year      = {2025},
  publisher = {Springer Nature Switzerland},
  address   = {Cham},
  pages     = {34--49},
  isbn      = {978-3-031-97100-6}
}

@software{beth2025klocal_code,
  author    = {Beth, Christian and Fleischmann, Pamela and Huch, Annika
               and Kazempour, Daniyal and Kr{\"o}ger, Peer
               and Kulow, Andrea and Renz, Matthias},
  title     = {{k-local Graphs} -- Code},
  year      = {2025},
  doi       = {10.5281/zenodo.20557725},
  url       = {https://github.com/c-beth/k-local-graphs}
}

The code is available under the MIT License.

Dependencies

# Python >= 3.8
numpy
networkx
matplotlib
pandas

Install dependencies with:

pip install -r requirements.txt

Usage

The file main.py contains a working example demonstrating how to construct a graph, run all three approaches (naive, priority search, and depth-first search), and visualize the result.

python main.py

Example Dataset

The data/DBLP4areas/ directory contains the DBLP subset used in the experiments in the paper, covering the areas of databases, data mining, machine learning, and information retrieval. It can be used as a starting point for exploring the $k$-locality of a real-world heterogeneous graph.

Tests

Unit tests for the correctness of all three approaches are provided in test/test_k_locality.py and can be run with:

python -m pytest test/test_k_locality.py

License

This project is licensed under the MIT License.