Offensive Security Researcher & Quantum Cryptography Analyst

Maximum Cardinality Search Algorithm: Working, Explanation, and Applications

Abdul Wahab Junaid
Maximum Cardinality Search algorithm and working of this algorithm

Maximum Cardinality Search algorithm and working of this algorithm

I want to introduce Maximum Cardinality Search (MCS) as a graph-traversal algorithm I find deceptively simple but very powerful for a specific purpose: testing whether a graph is chordal (every cycle of length four or more has a “chord” — an edge connecting two non-adjacent vertices in the cycle), and, if it is, producing a perfect elimination ordering of its vertices. I care about this because chordal graphs and perfect elimination orderings show up constantly in sparse matrix factorization, database query optimization, and probabilistic graphical models.

History and Background

Maximum Cardinality Search was introduced by Robert E. Tarjan and Mihalis Yannakakis in their 1984 paper “Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs.” Their contribution was showing that a very simple greedy vertex-selection rule — always pick the next vertex with the most already-visited neighbors — produces an ordering that can be used to test chordality and compute a perfect elimination ordering, all in linear time, which was a significant improvement over previously known methods for this class of problems.

Problem Statement

I define the core problem MCS addresses as: given an undirected graph $G = (V, E)$, produce a vertex ordering $v_1, v_2, \dots, v_n$ such that, when combined with a follow-up check, I can determine whether $G$ is chordal, and if so, obtain a perfect elimination ordering — an ordering where, for every vertex $v_i$, the neighbors of $v_i$ that come later in the ordering form a clique (a fully connected subgraph).

Core Concepts

How It Works

  1. I initialize a “visited count” (cardinality) of 0 for every vertex.
  2. I pick an arbitrary starting vertex, assign it the highest label ($n$, since MCS labels vertices in reverse-elimination order), and mark it as visited.
  3. For every remaining unvisited vertex, I increase its cardinality count by 1 for each visited neighbor it has.
  4. I select the unvisited vertex with the maximum cardinality (breaking ties arbitrarily), assign it the next label, and mark it as visited.
  5. I repeat steps 3–4 until all vertices are labeled, producing the full MCS ordering.
  6. To test chordality, I verify that the resulting ordering is a perfect elimination ordering: for each vertex (processed in reverse label order), I check whether its neighbors that come earlier in the elimination sequence form a clique.

Working Principle

The core logic behind MCS is a simple greedy heuristic: by always advancing to the vertex most strongly “connected” to what’s already been processed, the algorithm naturally tends to peel graphs apart clique by clique when the graph is chordal. Tarjan and Yannakakis proved that this greedy rule — despite its simplicity — always produces an ordering that, for chordal graphs, is guaranteed to be a valid perfect elimination ordering (or can be trivially checked and confirmed as one), whereas for non-chordal graphs, the verification step will find neighbors that don’t form a clique, correctly detecting the lack of chordality.

Mathematical Foundation

I express the cardinality update rule as: for a vertex $v$ still unvisited, its cardinality $\text{card}(v)$ is:

$$ \text{card}(v) = |{u \in N(v) : u \text{ already visited}}| $$

where $N(v)$ is the neighbor set of $v$. At each step, I select:

$$ v_{\text{next}} = \arg\max_{v \text{ unvisited}} \text{card}(v) $$

A graph $G$ is chordal if and only if it admits a perfect elimination ordering $\sigma$ such that, for every vertex $v_i$:

$$ N(v_i) \cap {v_{i+1}, \dots, v_n} \text{ is a clique in } G $$

Diagrams

flowchart TD
    Start([Start: pick arbitrary vertex, label n]) --> Cardinality[Update cardinality of unvisited neighbors]
    Cardinality --> Select[Select unvisited vertex with max cardinality]
    Select --> Label[Assign next lower label, mark visited]
    Label --> Check{Unvisited vertices remain?}
    Check -- Yes --> Cardinality
    Check -- No --> Verify[Verify perfect elimination ordering]
    Verify --> End([Return ordering and chordality result])

Pseudocode

function MaximumCardinalitySearch(Graph):
    n = number of vertices
    cardinality[v] = 0 for all v
    visited[v] = false for all v
    order = array of size n

    for i from n downto 1:
        v = unvisited vertex with maximum cardinality[v]
        order[i] = v
        visited[v] = true
        for each neighbor u of v:
            if not visited[u]:
                cardinality[u] += 1

    return order

function IsChordal(Graph, order):
    position[v] = index of v in order, for all v

    for i from 1 to n:
        v = order[i]
        laterNeighbors = { u in neighbors(v) : position[u] > position[v] }
        if laterNeighbors is not a clique in Graph:
            return false

    return true

Step-by-Step Example

Using the graph above: edges A-B, A-C, B-C, B-D, C-D, D-E. This graph is chordal (the 4-cycle A-B-D-C-A has chord B-C).

Resulting order (from label 1 to 5): A, C, B, D, E.

Checking the perfect elimination property: A’s later neighbors (in order) are C and B — is {C,B} a clique? Yes, B-C is an edge. C’s later neighbors are B and D — is {B,D} a clique? Yes, B-D is an edge. B’s later neighbor is D — trivially a clique (single vertex). D’s later neighbor is E — trivially a clique. This confirms the ordering is a valid perfect elimination ordering, so the graph is chordal.

Time Complexity

MCS runs in $O(V + E)$ time when implemented with appropriate bucket-based data structures (grouping vertices by their current cardinality value, so I can find and update the maximum-cardinality vertex in constant amortized time per operation). This linear-time bound holds regardless of input arrangement — best, average, and worst case are all $O(V+E)$. The follow-up chordality verification step also runs in $O(V+E)$ time using a similarly careful implementation, so the combined chordality test is linear overall.

Space Complexity

I need $O(V)$ space for cardinality counts, visited flags, labels, and the bucket structure used to track vertices by current cardinality, plus $O(V+E)$ for the adjacency list representation of the graph — overall space is $O(V+E)$.

Correctness Analysis

The correctness of MCS as a chordality test rests on a theorem proved by Tarjan and Yannakakis: if a graph is chordal, then the MCS ordering (produced by the simple greedy cardinality rule) is guaranteed to be a perfect elimination ordering. This is because, in a chordal graph, the greedy cardinality-maximizing choice always corresponds to peeling off a simplicial vertex relative to the remaining unvisited set — the specific greedy rule aligns exactly with the recursive clique structure that chordality guarantees exists. If the graph is not chordal, no perfect elimination ordering exists at all, so the verification step (checking that later-neighbors form a clique at every vertex) will necessarily fail somewhere, correctly reporting non-chordality. Because the verification step directly checks the defining property of a PEO, the overall test is exact — no chordal graph is misclassified as non-chordal, and vice versa.

Advantages

Disadvantages

Applications

Implementation in C

#include <stdio.h>
#include <stdbool.h>

#define V 5  // A=0, B=1, C=2, D=3, E=4

int graph[V][V] = {
    {0,1,1,0,0},
    {1,0,1,1,0},
    {1,1,0,1,0},
    {0,1,1,0,1},
    {0,0,0,1,0}
};

void maximumCardinalitySearch(int order[]) {
    int cardinality[V] = {0};
    bool visited[V] = {false};

    for (int i = V - 1; i >= 0; i--) {
        int best = -1, bestCard = -1;
        for (int v = 0; v < V; v++) {
            if (!visited[v] && cardinality[v] > bestCard) {
                bestCard = cardinality[v];
                best = v;
            }
        }
        order[i] = best;
        visited[best] = true;
        for (int u = 0; u < V; u++) {
            if (graph[best][u] && !visited[u]) {
                cardinality[u]++;
            }
        }
    }
}

bool isClique(int vertices[], int count) {
    for (int i = 0; i < count; i++)
        for (int j = i + 1; j < count; j++)
            if (!graph[vertices[i]][vertices[j]])
                return false;
    return true;
}

bool isChordal(int order[]) {
    int position[V];
    for (int i = 0; i < V; i++)
        position[order[i]] = i;

    for (int i = 0; i < V; i++) {
        int v = order[i];
        int laterNeighbors[V], count = 0;
        for (int u = 0; u < V; u++) {
            if (graph[v][u] && position[u] > position[v]) {
                laterNeighbors[count++] = u;
            }
        }
        if (!isClique(laterNeighbors, count))
            return false;
    }
    return true;
}

int main() {
    int order[V];
    maximumCardinalitySearch(order);

    printf("MCS order (label 1 to %d): ", V);
    for (int i = 0; i < V; i++)
        printf("%d ", order[i]);
    printf("\n");

    if (isChordal(order))
        printf("The graph IS chordal.\n");
    else
        printf("The graph is NOT chordal.\n");

    return 0;
}

Sample Input and Output

Input: the graph above (A=0, B=1, C=2, D=3, E=4) with edges A-B, A-C, B-C, B-D, C-D, D-E.

Output:

MCS order (label 1 to 5): 0 2 1 3 4
The graph IS chordal.

This corresponds to my manual ordering A, C, B, D, E, confirming the graph is chordal.

Optimization Techniques

Common Mistakes

Further Reading

Exit mobile version