GitHub - RyanGibb/apt-graph-colouring: Using the APT Debian package manager to solve graph m-colouring problems

2 min read Original article ↗

Transform graph m-colouring problems into Debian repositories and solve them using APT's dependency resolver.

Requirements

  • Python 3
  • apt (the Debian package manager)

On NixOS:

or

nix shell nixpkgs#apt nixpkgs#python3

Usage

# Generate and solve in one step
python3 colouring2apt.py <graph.col> <num_colours> <output_dir> --solve

# Or generate repo only
python3 colouring2apt.py <graph.col> <num_colours> <output_dir>

Examples

# Solve myciel3 with 4 colours (should succeed, χ=4)
python3 colouring2apt.py instances/myciel3.col 4 /tmp/repo --solve

# Try with 3 colours (should fail)
python3 colouring2apt.py instances/myciel3.col 3 /tmp/repo --solve

Graph Colouring Instances

The instances/ directory is for DIMACS-format benchmarks.

The following instances:

File Nodes Edges Chromatic Number
myciel3.col 11 20 4
myciel4.col 23 71 5
myciel5.col 47 236 6
myciel6.col 95 755 7
myciel7.col 191 2360 8
queen5_5.col 25 160 5

Can be obtained with:

cd instances
curl -fsSL -O https://mat.tepper.cmu.edu/COLOR/instances/myciel3.col \
           -O https://mat.tepper.cmu.edu/COLOR/instances/myciel4.col \
           -O https://mat.tepper.cmu.edu/COLOR/instances/myciel5.col \
           -O https://mat.tepper.cmu.edu/COLOR/instances/myciel6.col \
           -O https://mat.tepper.cmu.edu/COLOR/instances/myciel7.col \
           -O https://mat.tepper.cmu.edu/COLOR/instances/queen5_5.col

Browse more instances at:

Output Format

On success, outputs DIMACS solution format to stdout:

s col 4
l 1 4
l 2 2
l 3 4
...

On failure, prints "No N-colouring exists" to stderr and exits with code 1.

How It Works

The reduction encodes an m-colouring problem as a Debian package dependency problem:

  1. Each graph node N becomes a package nN with M versions (one per colour)
  2. Each edge (u,v) creates conflicts: nu version K conflicts with nv version K for all K
  3. A root package depends on all node packages with any version

APT's dependency resolver then finds a consistent assignment of versions (colours) to packages (nodes).

DIMACS Format

Input (.col files):

c Comment lines start with 'c'
p edge <nodes> <edges>
e <node1> <node2>
...

Output (solution):

s col <num_colours>
l <node> <colour>
...