goatd: Greatest Of All Tree Decompositions
Paste a PACE .gr graph, open or drop a
file, or pick an example, and goatd returns a tree decomposition; the
solver runs in this tab and nothing is uploaded. The same solver is a
Rust crate with a
command-line tool, a Python
package and a C
library; the code and its documentation are
on GitHub. The
solver comparison sets it against seven public
solvers on graphs from model-counting formulas.
loading the solver
Result
Once there is a decomposition, hover a vertex to see the bags that hold it: they form a connected piece of the tree, the running intersection property. Hover an edge to see the bags that hold both its ends; every edge has at least one.
Hover a bag to see it separate the graph. The vertices beyond each branch of the tree at that bag get a colour of their own, and no edge joins two colours.
Press Decompose.