# Partitioning a Graph into Low-Diameter Clusters

[![INFORMS Journal on Computing Logo](https://INFORMSJoC.github.io/logos/INFORMS_Journal_on_Computing_Header.jpg)](https://pubsonline.informs.org/journal/ijoc)

This archive is distributed in association with the [INFORMS Journal on
Computing](https://pubsonline.informs.org/journal/ijoc) under the [GNU General Public License v3.0](LICENSE).

The software and data in this repository are a snapshot of the software and data
that were used in the research reported on in the paper
[Partitioning a Graph into Low-Diameter Clusters](https://doi.org/10.1287/ijoc.2025.1448) by Jack Zhang, Lucas Silveira, Hamidreza Validi, Logan Smith, Austin Buchanan, and Illya V. Hicks.

**Important: This code is being developed on an on-going basis at
[https://github.com/JackDaihanZhang/Partitioning-a-graph-into-low-diameter-clusters](https://github.com/JackDaihanZhang/Partitioning-a-graph-into-low-diameter-clusters).
Please go there if you would like to get a more recent version or would like support.**

## Cite

To cite the contents of this repository, please cite both the paper and this repo, using their respective DOIs.

https://doi.org/10.1287/ijoc.2025.1448

https://doi.org/10.1287/ijoc.2025.1448.cd

Below is the BibTeX for citing this snapshot of the repository.

```
@article{zhang2025partitioning,
  author =    {Jack Zhang and Lucas Silveira and Hamidreza Validi and Logan Smith and Austin Buchanan and Illya V. Hicks},
  publisher = {INFORMS Journal on Computing},
  title =     {{Partitioning a Graph into Low-Diameter Clusters}},
  year =      {2026},
  doi =       {10.1287/ijoc.2025.1448.cd},
  url =       {https://github.com/INFORMSJoC/2025.1448},
  note =      {Available for download at https://github.com/INFORMSJoC/2025.1448},
}
```

## Description

The goal of this software is to solve the minimum *s*-club partitioning and covering problems. Given a graph *G = (V, E)*, the minimum *s*-club partitioning problem seeks a partition of the vertex set into the fewest parts such that the diameter of each part in its induced subgraph is at most *s*. The minimum *s*-club covering problem is the relaxation that allows parts to overlap.

This paper studies these problems from the lenses of approximation algorithms and integer programming. We give Õ(*n*<sup>1/2</sup>)-approximation algorithms for any even integer *s*, and prove matching inapproximability results. We develop new MIP-based heuristics (inspired by the approximation algorithms) that perform extremely well in practice, and propose a MIP formulation with an exponentially large class of cut-like inequalities solved via a branch-and-cut algorithm.

The following figures show a minimum 2-club and 3-club partition for the social network of [Zachary's karate club](https://en.wikipedia.org/wiki/Zachary%27s_karate_club).

A minimum 2-club partition             |  A minimum 3-club partition
:-------------------------:|:-------------------------:
![](docs/karate_s2.png?raw=true "a minimum 2-club partition of the karate graph")   |  ![](docs/karate_s3.png?raw=true "a minimum 3-club partition of the karate graph")

## Dependencies

To run the code, you will need:

- [Python 3](https://www.python.org/) (tested with Python 3.8+)
- [Gurobi Optimizer](https://www.gurobi.com/) with a valid license
- [gurobipy](https://pypi.org/project/gurobipy/) Python package
- [NetworkX](https://networkx.org/) Python package

## Repository Structure

```
2025.1448/
├── README.md          # This file
├── AUTHORS            # Author contact information
├── LICENSE            # GNU General Public License v3.0
├── src/               # Source code and configuration files
│   ├── main.py        # Main entry point
│   ├── callback.py    # Gurobi callback functions (lazy constraints)
│   ├── heuristic.py   # Heuristic methods
│   ├── lb.py          # Lower bound computation
│   ├── read.py        # Graph input parsing
│   ├── check_solution.py  # Solution verification
│   ├── s_club_ext_label.py  # Extended label formulation
│   ├── sasha.py       # Sasha formulation
│   └── *.json         # Configuration files for experiments
├── data/              # Instance data
│   ├── *.graph        # Graph instances in various formats
│   ├── *.txt          # Graph instances in edge-list format
│   ├── *.gml          # Graph instances in GML format
│   ├── Barabasi/      # Barabási–Albert random graph instances
│   ├── gnp/           # Erdős–Rényi G(n,p) random graph instances
│   └── random graphs/ # Random regular graph instances
├── results/           # Raw computational results (CSV)
└── docs/              # Figures used in this README
```

## Replicating

To replicate the experiments in the paper, navigate to the `src/` directory and run the main script with the appropriate configuration file. For example:

```bash
cd src
python main.py config_table_2_new.json 1>>log-file.txt 2>>error-file.txt
```

The configuration files correspond to the tables in the paper:

| Config File | Paper Table |
|---|---|
| `config_table_2_new.json` | Table 2 |
| `config_table_3_new.json` | Table 3 |
| `config_table_4_new.json` | Table 4 |
| `config_table_5_new.json` | Table 5 |
| `config_table_6_new.json` | Table 6 |
| `config_table_7_new.json` | Table 7 |

Additional configuration files are provided for the Barabási–Albert, G(n,p), and random graph experiments used in the covering and partitioning formulations.

### Configuration Options

Each run in a configuration file specifies:

- `"Problem"`: one of `{"LB+UB", "Partitioning", "Covering"}`
- `"Model"`: one of `{"IP", "APX", "GRE", "ext_label", "Sasha"}`
- `"s"`: an integer ≥ 2 (the diameter bound)
- `"Instance"`: the name of a graph instance (e.g., `"karate"`, `"dolphins"`, `"football"`, `"jazz"`, etc.)

## Results

The `results/` directory contains the raw computational results reported in the paper as CSV files, one per table.

## Ongoing Development

This code is being developed on an on-going basis at [https://github.com/JackDaihanZhang/Partitioning-a-graph-into-low-diameter-clusters](https://github.com/JackDaihanZhang/Partitioning-a-graph-into-low-diameter-clusters). Please go there if you would like to get a more recent version or would like support.

## Support

For questions or issues, please contact the authors (see [AUTHORS](AUTHORS)) or open an issue at the [development repository](https://github.com/JackDaihanZhang/Partitioning-a-graph-into-low-diameter-clusters).
