Given a chordal graph $G$, what is the complexity of computing the reduced clique graph $C_r(G)$?

Question

A graph $G$ is chordal if it doesn't have induced cycles of length $4$ or more. A clique tree $T$ of $G$ is a tree in which the vertices of the tree are the maximal cliques of $G$. An edge in $T$ corresponds to a minimal separator. The number of distinct clique trees can be exponential in the number of vertices in a chordal graph.

The reduced clique graph $C_r(G)$ is the union of all clique trees of $G$. That is, it has all the same vertices, and all possible edges. What is the complexity of computing $C_r(G)$ for a given $G$?

I think I once saw a presentation claiming $C_r(G)$ can be computed in $O(m+n)$ time without proof. This would mean it is as easy as computing a clique tree of $G$. Is there a reference that confirms this, or gives a slower algorithm for computing it?

Answer 1

The complexity is O(nm)... from G compute the maximal cliques and make them vertices in your graph H (initially with no edges)... then compute all minimal separators and order them by size... pick the largest separator S and make any two cliques C,C' adjacent in H (connect them by an edge with label S) if C,C' both contain S and are in different connected components of H (initially this is of course always true, but may not be later)... then pick next largest separator and do the same... repeat until all separators are processed... the resulting graph H is the reduced clique graph of G... computing maximal cliques and minimal separators takes O(n+m)... there are O(n) cliques and O(n) separators... the rest of the construction is O(nm) as processing each separator can take O(m) time... ... this cannot be improved below O(n^2) unless you can solve the following problem: given a graph G find two vertices u,v such that N(u) contains N(v)... the latter is not known to have O(n+m) solution... ... it is therefore unlikely that a O(n+m) algorithm for computing reduced clique graphs is possible...

see Section 5 in M. Habib, J. Stacho: Polynomial-time algorithm for the leafage of chordal graphs, In: Algorithms - ESA 2009, Lecture Notes in Computer Science 5757/2009, pp. 290-300. (http://www.cs.toronto.edu/~stacho/public/leafage-esa1.pdf)