Obtaining a tree decomposition from an elimination

问题:

I need a nice tree decomposition of a graph given an elimination ordering and a chordalization of the graph.

My idea is to obtain all cliques in the graph (which I can do) and build a binary tree starting from a root and make children (i.e., cliques) depending on how many veritices the cliques have in common. I want to do this until all cliques are used and hence, I have a tree. The problem is that the cliques could have more than 2 vertices so I can not recursively run for each vertex as then, the tree might not be binary.

http://en.wikipedia.org/wiki/Tree_decomposition http://en.wikipedia.org/wiki/Chordal_graph

I am doing an implementation in python and currently I have the chordal graph, a list of all cliques and an elimination ordering. Ideas, and/or code are more than welcome!

回答1:

To construct a non-nice (in general) tree decomposition of a chordal graph: find a perfect elimination ordering, enumerate the maximal cliques (the candidates are a vertex and the neighbors that appear after it in the ordering), use each clique as a decomposition node and connect it to the next clique in the ordering that it intersects. I didn't describe that quite right; see my subsequent answer.

A nice tree decomposition is defined as follows (definition from Daniel Marx). Nice tree decompositions are rooted. Each node is of one of four types.

Leaf (no children): a set {v}
Introduce (exactly one child): a set S union {v} with child S (v not in S)
Forget (exactly one child): a set S with child S union {v} (v not in S)
Join (exactly two children): a set S with children S and S

Root the non-nice tree decomposition arbitrarily and start a recursive conversion procedure at the root. If the current node has no children, then construct the obvious chain consisting of a leaf node with introduce ancestors. Otherwise, observe that, if some vertex belongs to at least two children, then it belongs to the current node. Recursively convert the children and chain forget ancestors until their sets are subsets of the current node's. The easiest way to proceed in theory is to introduce the missing elements to each child, then join en masse. Since the running time of the next step, however, often depends exponentially on the set size, it might be wise to try some heuristics to join children before their subsets are complete.