the problem of finding a pseudo tree of (minimal height/depth or minimal induced width) is known to be NP-complete. This problem is found in various tasks (e.g. finding the smallest possible OR Search Graph). Greedy algorithms and polynomial-time heuristic schemes are available
2 Schemes
Given a graphical model 𝒢 and an ordering 𝑑:
- the DFS Spanning Tree generated by traversing the induced-order graph starting at the first variable of its ordering 𝑑 is a pseudo tree
- the hypergraph tree-decomposition / bucket tree derived from the induced ordered graph along 𝑑 of 𝒢, 𝑇=(𝑋, 𝐸) with 𝐸 = {(𝑋𝑖,𝑋𝑗) | (𝐵𝑋𝑖,𝐵𝑋𝑗) ∊ 𝑏𝑢𝑐𝑘𝑒𝑡 - 𝑡𝑟𝑒𝑒} is a pseudo tree of 𝒢
Greedy Search
eliminate node with the smallest cost
- min-neighbors/degree heuristic - number of neighbors in the current graph
- min-weight heuristic - weight (number of values) of factor formed
- min-fill heuristic - number of new fill edges to the current graph
- weighted min-fill heuristic - total weight of new fill edges (edge weight = product of weights of the 2 nodes)
Since an induced-ordered graph can be a starting point in generating a pseudo tree, the question is if the min-fill ordering heuristic which appears to be quite good for finding small induced-width is also good for finding pseudo trees with small heights
It is generally observed that:
- min-fill heuristic generates lower induced width pseudo trees
- hypergraph heuristic produces much smaller depth pseudo trees