Elimination Ordering#
Many algorithms for NPhard problems are exponential in treewidth. However, finding a lower bound on treewidth is in itself NPcomplete. [GD] describes a branchandbound algorithm for computing the treewidth of an undirected graph by searching in the space of perfect elimination ordering of vertices of the graph.
A clique of a graph is a fullyconnected subset of vertices; that is, every pair of vertices in the clique share an edge. A simplicial vertex is one whose neighborhood induces a clique. A perfect elimination ordering is an ordering of vertices \(1..n\) such that any vertex \(i\) is simplicial for the subset of vertices \(i..n\).

Provides a variable elimination order for a Chimera graph. 

Calculates the width of the tree decomposition induced by a variable elimination order. 

Determines whether a node n in G is almost simplicial. 

Determines whether a node n in G is simplicial. 
Computes an upper bound on the treewidth of graph G based on the maxcardinality heuristic for the elimination ordering. 

Computes a lower bound for the treewidth of graph G. 

Computes an upper bound on the treewidth of graph G based on the minfill heuristic for the elimination ordering. 

Computes an upper bound on the treewidth of graph G based on the minwidth heuristic for the elimination ordering. 


Provides a variable elimination order for the Pegasus graph. 

Computes the treewidth of graph G and a corresponding perfect elimination ordering. 
References#
Gogate & Dechter. “A Complete Anytime Algorithm for Treewidth.” https://arxiv.org/abs/1207.4109