Chordal Graphs, in depth: perfect elimination orderings, linear-time recognition, clique trees, and fill-in from sparse Cholesky to junction trees

Definition and first examples

Take a cycle a, b, c, d and back to a. With no chord it is an induced four-cycle, written C4, and the graph is not chordal. Add the edge a to c and the cycle splits into two triangles; the graph becomes chordal. Trees are chordal, because they have no cycles at all. Complete graphs are chordal. Interval graphs, where vertices are intervals on a line and edges mean overlap, are chordal, which is one reason scheduling problems on intervals are easy.

Chordality is hereditary: every induced subgraph of a chordal graph is chordal, since deleting vertices cannot create an induced cycle. Chordal graphs are also perfect, meaning the chromatic number equals the clique number on every induced subgraph; the perfect graphs article covers that family and shows the one-pass optimal colouring. Here the focus is the structure that makes such algorithms work and the places it shows up in engineering.

Simplicial vertices and perfect elimination orderings

A vertex is simplicial when its neighbours are pairwise adjacent, so the vertex and its neighbourhood form a clique. Dirac proved in 1961 that every chordal graph has a simplicial vertex, and in fact two non-adjacent ones unless the graph is complete. Remove a simplicial vertex and the rest is still chordal, so it has another simplicial vertex, and so on.

Recording the removal sequence gives a perfect elimination ordering, or PEO: an order v1, v2, ..., vn such that for each vi, the neighbours that come later in the order form a clique. Fulkerson and Gross showed in 1965 that a graph is chordal if and only if it has a PEO. That equivalence is the whole toolkit. Given a PEO, a set {v} + later neighbours is a clique for every v; every maximal clique is one of these n sets, so a chordal graph has at most n maximal cliques, while a general graph can have exponentially many.

Scanning repeatedly for a simplicial vertex is slow; the trick is to build the order in reverse with a search, then check it once.

Recognition with maximum cardinality search

Maximum cardinality search, from Tarjan and Yannakakis (1984), numbers vertices one at a time. At each step it picks an unnumbered vertex with the most already-numbered neighbours, breaking ties arbitrarily. If the graph is chordal, the reverse of the visiting order is a PEO. Lexicographic breadth-first search, from Rose, Tarjan and Lueker (1976), has the same property with a different tie rule. Both run in O(n + m) with bucket structures. Note the direction: the search order is the reverse of the elimination order, and getting this backwards is the most common bug in implementations.

def mcs_order(adj):
    # adj: dict vertex -> set of neighbours. Returns the visiting order;
    # reversed, it is a PEO if and only if the graph is chordal.
    n = len(adj)
    weight = {v: 0 for v in adj}
    buckets = [set() for _ in range(n + 1)]
    buckets[0] = set(adj)
    numbered, order, top = set(), [], 0
    for _ in range(n):
        while not buckets[top]:
            top -= 1
        v = buckets[top].pop()
        order.append(v)
        numbered.add(v)
        for u in adj[v]:
            if u not in numbered:
                buckets[weight[u]].discard(u)
                weight[u] += 1
                buckets[weight[u]].add(u)
        top += 1          # a weight rose by at most one this step
    return order

Each edge moves one vertex between adjacent buckets once, and the pointer top rises by at most one per step, so its total movement is bounded by 2n. That is linear time. On a non-chordal graph MCS still returns an order; it is simply not a PEO. Which is why the algorithm is search plus verification.

Checking the ordering in linear time

Checking a candidate order directly, by testing each vertex's later neighbourhood for being a clique, can cost the sum of squared degrees. Tarjan and Yannakakis give a linear check. For each vertex v, let its parent be the earliest later neighbour. If v's later neighbourhood is a clique, then every other later neighbour of v must be adjacent to the parent, and that is also sufficient when the condition holds for all vertices. So instead of testing pairs, each vertex hands its other later neighbours to its parent as adjacency demands, and each vertex checks its demands against its own neighbour set:

def is_peo(adj, peo):
    pos = {v: i for i, v in enumerate(peo)}      # peo[0] is eliminated first
    need = {v: set() for v in adj}
    for v in peo:
        later = [u for u in adj[v] if pos[u] > pos[v]]
        if later:
            parent = min(later, key=pos.__getitem__)
            need[parent].update(u for u in later if u != parent)
    return all(need[v] <= adj[v] for v in adj)

def is_chordal(adj):
    return is_peo(adj, mcs_order(adj)[::-1])

The demands handed out total at most m, and each subset test is linear in the demand set, so the check is O(n + m). On C4, whatever order MCS produces, the first eliminated vertex has two later neighbours that are not adjacent, and the parent's demand fails. These functions were tested against a brute-force chordless-cycle search on thousands of random small graphs.

Worked example

Take vertices A to G with edges AB, AC, BC, BD, CD, CE, DE, DF, EF and FG. Run MCS starting at A and break ties alphabetically. A is numbered; B and C each have weight 1. Pick B; C rises to 2 and D to 1. Pick C; D rises to 2 and E to 1. Pick D; E rises to 2 and F to 1. Pick E; F rises to 2. Pick F; G rises to 1. Pick G. The visiting order is A, B, C, D, E, F, G, so the candidate PEO is its reverse: G, F, E, D, C, B, A.

Check it. G's later neighbours are {F}, trivially a clique. F's are {D, E}, adjacent. E's are {C, D}, adjacent. D's are {B, C}, adjacent. C's are {A, B}, adjacent. B's are {A}. The order is perfect, so the graph is chordal. The candidate cliques are FG, DEF, CDE, BCD, ABC, AB and A; dropping the two contained in others leaves five maximal cliques, at most n as promised.

Maximal cliques and the clique tree

Gavril showed in 1974 that chordal graphs are exactly the intersection graphs of subtrees of a tree. The constructive form is the clique tree: a tree whose nodes are the maximal cliques, arranged so that for every vertex, the cliques containing it form a connected subtree. That is the running intersection property, and the edge between two adjacent cliques is labelled with their intersection, a minimal separator of the graph.

A clique tree can be built as a maximum-weight spanning tree on the clique intersection graph, with weight equal to the size of the intersection. That is simple and correct, but quadratic in the number of cliques; production implementations read the tree off the PEO in linear time by attaching each clique to the clique of its vertex's parent.

def maximal_cliques(adj, peo):
    pos = {v: i for i, v in enumerate(peo)}
    cand = [frozenset([v, *(u for u in adj[v] if pos[u] > pos[v])]) for v in peo]
    return [c for c in set(cand) if not any(c < d for d in cand)]

def clique_tree(cliques):                      # Kruskal on |Ci & Cj|, largest first
    edges = sorted(((len(a & b), i, j) for i, a in enumerate(cliques)
                    for j, b in enumerate(cliques) if i < j and a & b), reverse=True)
    root = list(range(len(cliques)))
    def find(x):
        while root[x] != x:
            root[x] = root[root[x]]
            x = root[x]
        return x
    tree = []
    for w, i, j in edges:
        if find(i) != find(j):
            root[find(i)] = find(j)
            tree.append((i, j, cliques[i] & cliques[j]))
    return tree

On the example the tree is the path ABC, BCD, CDE, DEF, FG with separators BC, CD, DE and F. Removing any separator disconnects the graph, which is exactly what a divide-and-conquer or message-passing algorithm exploits.

Elimination and fill-in in sparse Cholesky

Gaussian elimination on a symmetric sparse matrix, as in Cholesky factorisation, has a graph reading. Vertices are rows, edges are non-zero off-diagonal entries. Eliminating a vertex makes its remaining neighbours pairwise adjacent, because the update writes non-zeros between every pair of them. Those new entries are fill-in, and they cost memory and floating-point work. The graph of the matrix plus its fill is always chordal, and the elimination order is a PEO for it. A matrix whose graph is already chordal, factored in PEO order, has zero fill.

The star in the figure is the arrow matrix. Ordering the dense row first fills the whole matrix; ordering it last produces no fill at all. Finding the order with minimum fill-in is NP-hard, as Yannakakis showed in 1981, so sparse solvers use heuristics: minimum degree and its approximate variant AMD for general matrices, and nested dissection, which recursively removes small separators, for meshes. A solver's symbolic phase computes this fill pattern before any arithmetic.

Junction trees and treewidth

Exact inference in a Bayesian network or Markov random field follows the same pattern. Moralise the network, triangulate it by choosing an elimination order and adding its fill, take the maximal cliques of the resulting chordal graph, and connect them into a clique tree, which the graphical-models literature calls a junction tree. Belief propagation on that tree is exact, and its cost is exponential in the size of the largest clique, because each clique carries a table over its variables.

The treewidth of a graph is the minimum, over all chordal supergraphs, of the largest clique size minus one. A tree has treewidth 1, a cycle has treewidth 2. Every elimination order gives an upper bound, and a tree decomposition is just a clique tree of some triangulation. Problems such as independent set, colouring and Hamiltonian path, hard in general by the reductions in NP-completeness, become dynamic programs over the decomposition, linear in n and exponential only in the width. That is why a good triangulation is worth real engineering effort.

Problems that become easy

On a chordal graph with a PEO, several problems that are hard in general become linear. Maximum clique is the largest candidate set. Minimum colouring is greedy colouring in reverse PEO order, which uses exactly the clique number of colours, the subject of the graph colouring article. Maximum independent set is greedy in PEO order: take a vertex, discard its neighbours, repeat, and the result is optimal. Minimum clique cover follows from the same pass. Compare the general clique reductions, where none of this holds. Register allocation is a classic application: interference graphs of programs in SSA form are chordal, so optimal colouring is polynomial there.

Failure modes

• Using the search order as the elimination order. MCS and LexBFS emit the reverse of a PEO. Using it forwards fails on most chordal graphs and occasionally passes, which is worse.
• Skipping the verification. MCS returns an order on every graph; without the check, non-chordal input yields wrong cliques and wrong colourings silently.
• A quadratic check called linear. Testing every pair of later neighbours costs the sum of squared degrees, which explodes on graphs with hubs.
• Expecting minimum fill from a heuristic. Minimum degree and nested dissection are good orders, not optimal ones, and a poor order on a large matrix can cost orders of magnitude.
• Ignoring clique size in a junction tree. A triangulation with one large clique makes inference infeasible regardless of how many small cliques there are.

Trade-offs

What to do next

1. Implement mcs_order and is_peo and test them against a brute-force chordless-cycle search on random small graphs.
2. Trace the worked example by hand, then check that your code produces the same five cliques.
3. Add a linear clique-tree construction from the PEO and verify the running intersection property.
4. Factor a sparse matrix with natural ordering and with AMD, and compare the fill reported by your solver.
5. Compute an elimination-order upper bound on the treewidth of a graph you care about.
6. When a problem on your graphs is NP-hard, test whether the graphs are chordal or have small treewidth first.