GraphsTreewidth.jl

A Julia package for solving NP-hard graph optimization problems using tree decomposition-based dynamic programming.

Supported Problems

• ColoringProblem - chromatic number
• VertexCoverProblem - vertex cover number
• DominatingSetProblem - domination number

Basic Usage

In order to solve an optimization problem, construct a Solver.

julia> using GraphsTreewidth, Graphs

julia> graph = smallgraph(:petersen)

julia> solver = Solver(graph)
Solver{SimpleGraph{Int64}}:
  width: 5
  bags: 5

If the solver has low width, then we can use it to solve problems.

julia> coloring = solve(ColoringProblem(), solver)
Coloring{Int64}(3, [2, 1, 3, 2, 3, 3, 3, 2, 1, 1])

julia> cover = solve(VertexCoverProblem(), solver)
6-element Vector{Int64}:
 2
 4
 5
 7
 8
 6

julia> domset = solve(DominatingSetProblem(), solver)
3-element Vector{Int64}:
 2
 4
 8

Performance

The library is remarkably performant.

julia> using Graphs, GraphsTreewidth

julia> graph = loadgraph("linverse.lgz") # sparse.tamu.edu/GHS_indef/linverse
{11999, 41989} undirected simple Int64 graph

julia> @time solver = Solver(graph);
  0.002426 seconds (71 allocations: 5.033 MiB)

julia> @time solve(ColoringProblem(), solver);
  0.003947 seconds (48.09 k allocations: 5.423 MiB)