Maximum Cardinality Search for Chordal Recognition

Maximum Cardinality Search and Chordal Graphs

A chordal graph has no induced cycle of length at least four. One way to recognize such a graph is to find a perfect elimination ordering: an ordering in which each vertex’s neighbors appearing later form a clique. Maximum cardinality search (MCS) is a simple rule for producing a candidate ordering. Its key feature is that the search order must be reversed before the clique tests are made.

All graphs in this tutorial are finite and simple. A set of vertices is a clique if every pair of distinct vertices in it is adjacent; the empty set and a one-vertex set count as cliques. An induced cycle is a cycle for which the subgraph induced by its vertices has no edges other than the cycle edges.

MCS constructs a selection order \(v_1,\dots,v_n\). Initially every vertex has label \(0\). At each step, select an unselected vertex with largest current label; when labels tie, any fixed tie-breaking rule may be used. Then increase by \(1\) the label of each unselected neighbor of the chosen vertex. The candidate PEO is the reverse order \(w_i=v_{n+1-i}\). In that reverse order, the vertices later than \(v_i\) are exactly the vertices selected before \(v_i\).

Proof. Initially no vertices have been selected, so every unselected vertex has zero selected neighbors and label \(0\). Suppose the statement holds just before a vertex \(v\) is selected. The algorithm increases the label of each unselected neighbor of \(v\) by \(1\), and leaves all other unselected labels unchanged. For each such neighbor, the number of selected neighbors has increased by exactly \(1\); for every other unselected vertex it has not changed. Thus the statement still holds after this step. Induction over the selection steps proves the claim. \(\square\)

The Recognition Test and Its Correctness

After MCS finishes, reverse the selection order and inspect each vertex’s later neighbors. The graph passes the test if every one of these sets is a clique. The following standard ordering theorem is the structural fact that makes this test a recognition algorithm.

In particular, the theorem applies to disconnected graphs and to graphs with isolated vertices. MCS need not be restarted separately in each component: when no unselected vertex has a positive label, the rule selects a vertex of label \(0\) from another component if one remains.

The acceptance direction can also be checked directly from the definitions, without using the MCS theorem. If an ordering is a PEO, the graph is chordal:

Proof. Suppose \(w_1,\dots,w_n\) is a PEO and, to obtain a contradiction, that the graph contains an induced cycle of length at least \(4\). Choose the vertex of that cycle appearing earliest in the ordering, say \(w_i\). Its two neighbors along the cycle both appear later than \(w_i\). They are distinct and are not adjacent: an edge between them would be a chord of the induced cycle. But the PEO condition says that all later neighbors of \(w_i\) form a clique, so those two neighbors must be adjacent. This contradiction shows that no such induced cycle exists. \(\square\)

Consequently, if the MCS test accepts, its reversed order is a PEO and the proposition shows that the graph is chordal. If the test rejects, the reversed order is not a PEO; the MCS ordering theorem then implies that the graph is not chordal. The failed clique check is a valid rejection certificate for this algorithm, though it does not by itself list an induced cycle.

Worked MCS Traces

Running Time and Implementation

Labels are integers between \(0\) and \(n-1\), because a vertex has at most \(n-1\) neighbors. A direct implementation can keep all unselected vertices in a max-priority queue. Insert each vertex initially with key \(0\). Whenever an unselected neighbor’s label increases, insert a new queue entry with its new key. When extracting a maximum, discard entries for already selected vertices or entries whose key is smaller than that vertex’s current label. Labels only increase, so an entry with a key different from the current label is stale.

There are \(n\) initial insertions and at most \(m\) label increases: each edge can cause an increase at most once, when its first endpoint is selected. Thus there are at most \(n+m\) insertions and at most \(n+m\) extractions, including stale entries. A binary heap therefore performs the search in \(O((n+m)\log(n+m))\) time when \(n+m\ge2\), using \(O(n+m)\) heap space. For the empty graph, the search and test take constant time.

For a direct clique test, let \(k_v\) be the number of later neighbors of vertex \(v\) in the reversed order. Checking all unordered pairs in each later-neighbor set takes \(\sum_{v\in V}\binom{k_v}{2}\) adjacency queries. With adjacency sets providing constant-time membership queries, the expected verification time is \(O(n+m+\sum_v\binom{k_v}{2})\); the additional \(n+m\) accounts for storing the graph and iterating over its vertices and edges. With a deterministic representation, such as sorted adjacency lists, each pair query can instead use binary search, giving \(O(n+m+\sum_v\binom{k_v}{2}\log n)\) verification time. Since \(k_v\le n-1\), this straightforward test can be quadratic or larger in dense cases. These bounds describe this implementation of the requested pairwise clique checks; more specialized implementations can reduce verification time.

Common Mistake

Testing the selection order instead of its reverse. Let \(V=\{0,1,2,3\}\) and \(E=\{01,02,03\}\), a star with center \(0\). With smallest-numbered tie-breaking, MCS selects \(0\) first, increasing the labels of \(1,2,3\) from \(0\) to \(1\), and then selects \(1,2,3\) in that order. The selection order is \(0,1,2,3\). If one mistakenly tests that order, vertex \(0\) has later neighbors \(\{1,2,3\}\), which is not a clique because none of the edges \(12,13,23\) is present. That incorrect test would reject a chordal graph. The correct order is the reverse, \(3,2,1,0\): each leaf has just one later neighbor, \(0\), and the center has no later neighbors. Every set passes, as required.