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?


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)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.