Elimination Ordering¶
Many algorithms for NP-hard problems are exponential in treewidth. However, finding a lower bound on treewidth is in itself NP-complete. [GD] describes a branch-and-bound 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 fully-connected 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\).
chimera_elimination_order(m[, n, t]) |
Provides a variable elimination order for a Chimera graph. |
elimination_order_width(G, order) |
Calculates the width of the tree decomposition induced by a variable elimination order. |
is_almost_simplicial(G, n) |
Determines whether a node n in G is almost simplicial. |
is_simplicial(G, n) |
Determines whether a node n in G is simplicial. |
max_cardinality_heuristic(G) |
Computes an upper bound on the treewidth of graph G based on the max-cardinality heuristic for the elimination ordering. |
minor_min_width(G) |
Computes a lower bound for the treewidth of graph G. |
min_fill_heuristic(G) |
Computes an upper bound on the treewidth of graph G based on the min-fill heuristic for the elimination ordering. |
min_width_heuristic(G) |
Computes an upper bound on the treewidth of graph G based on the min-width heuristic for the elimination ordering. |
pegasus_elimination_order(n[, coordinates]) |
Provides a variable elimination order for the Pegasus graph. |
treewidth_branch_and_bound(G[, …]) |
Computes the treewidth of graph G and a corresponding perfect elimination ordering. |
References¶
| [GD] | Gogate & Dechter. “A Complete Anytime Algorithm for Treewidth.” https://arxiv.org/abs/1207.4109 |