Obtaining a tree decomposition from an elimination ordering and chordal graph

Question

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!

Melidamelilot

I'm confused. The obvious tree decomposition here has a node for each clique and connections between the nodes according to the elimination order (i.e., a path). Are you seeking a nice (technical term) tree decomposition? – Cirrus

I do not know how the elimination order relates to the tree decomposition. In other words, once I have the cliques, how do I use the elimination order to build the tree? To answer your question, I am seeking a nice tree decomposition in the sense that I want each node (i.e., clique) to have at most two neighbors in the tree decomposition. I om not sure if that is done with the obvious tree decomposition you mentioned. – Melidamelilot

I must not be awake yet, since I thought that we were talking about interval graphs (derp). You do want a nice tree decomposition, and it's not trivial to obtain. I'll post an answer shortly. – Cirrus

Answer 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.

Cirrus

Thank you very much! That was what I was looking for, I was not aware of the term 'nice'. – Melidamelilot