goatd — Greatest Of All Tree Decompositions

Tree decompositions of graphs, as a Rust library and command-line solver. The portfolio runs several constructions and keeps the narrowest result:

• portfolio search — safe reductions, several seeds and construction methods, then optional separator refinement;
• greedy elimination — min-fill and min-degree, with deterministic or weighted-sampling tie breaking;
• nested dissection — recursive multilevel bisection, with each separator eliminated after its two sides;
• flow-based separation — balanced cuts for constructing and refining decompositions. goatd includes a Rust FlowCutter separator search and the vendored PACE 2017 FlowCutter decomposer.

See Algorithms for the details and the differences from the upstream methods.

Solver

cargo install goatd
goatd graph.gr > graph.td

goatd reads and writes the PACE .gr and .td formats. Choose --order minfill, mindegree, nested-dissection, flowcutter, or portfolio; run goatd --help for budgets, seeds, weighted ties, and refinement. The same solver runs in the browser.

Library

[dependencies]
goatd = "0.1"

The basic example constructs a graph, computes a decomposition, validates it, and writes it in PACE format:

cargo run --example basic

The public API also exposes graph and hypergraph bisection, the Rust separator search, the C++ FlowCutter decomposer, and decomposition projection and refinement. Rustdoc documents each entry point.

Bindings

The same constructions are available through Python, C and C++, and WebAssembly.

Evaluation

The solver comparison runs the shipped portfolio and seven public baselines on 9,413 selected component graphs derived from Model Counting Competition formulas. Each receives ten seconds on one CPU.

Solver	Nontrivial	Exact best	Within +1	Within +4
goatd portfolio	9,344 (99.3%)	8,745 (92.9%)	9,100 (96.7%)	9,199 (97.7%)
Jdrasil heuristic	9,095 (96.6%)	1,273 (13.5%)	2,676 (28.4%)	5,598 (59.5%)
Tamaki PACE 2017	8,240 (87.5%)	818 (8.7%)	1,457 (15.5%)	3,431 (36.4%)
HTD	9,139 (97.1%)	328 (3.5%)	473 (5.0%)	1,996 (21.2%)
FlowCutter PACE 2017	9,115 (96.8%)	320 (3.4%)	495 (5.3%)	2,215 (23.5%)
NetworkX min-degree	8,999 (95.6%)	138 (1.5%)	153 (1.6%)	241 (2.6%)
NetworkX min-fill	8,279 (88.0%)	65 (0.7%)	196 (2.1%)	1,595 (16.9%)
Arboretum heuristic	5,549 (59.0%)	35 (0.4%)	125 (1.3%)	1,032 (11.0%)

Every decomposition is checked by the same validator. The default selection omits graphs where pinned NetworkX min-degree returns a validated width below 30. “Nontrivial” means a validated decomposition narrower than |V| - 1. “Exact best” is the smallest width observed among the displayed solvers, not a proven optimum.

Building and contributing

Build setup is in Building. Contributions follow CONTRIBUTING.md.

Citing

goatd has no accompanying paper, so cite the software:

@misc{goatd,
  author       = {Van den Broeck, Guy},
  title        = {goatd: Greatest Of All Tree Decompositions},
  year         = {2026},
  howpublished = {\url{https://github.com/Tractables/goatd}},
  note         = {Rust library and command-line solver, version 0.1.2}
}

Licence

Apache-2.0. Vendored code and modifications are recorded in THIRD-PARTY.md; ACKNOWLEDGEMENTS.md credits the work behind the algorithms.