# 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 |