Skip to content

Chordal Graphs

Chordal graphs are a special class of graphs: many problems that are NP-hard on general graphs have efficient linear-time algorithms on chordal graphs.

Definitions and properties

Subgraph: a graph whose vertex set and edge set are subsets of the vertex set and edge set of the original graph.

Induced subgraph: a graph whose vertex set is a subset of the original vertex set and whose edge set consists of all edges with both endpoints in the chosen vertex set.

Clique: a complete subgraph.

Maximal clique: a clique that is not a subgraph of any other clique.

Maximum clique: a clique with the largest number of vertices.

Clique number: the number of vertices of a maximum clique, written \(\omega(G)\).

Minimum coloring: a coloring of the vertices with the fewest colors such that the two endpoints of every edge get different colors.

Chromatic number: the number of colors in a minimum coloring, written \(\chi(G)\).

Maximum independent set: a largest set of vertices no two of which are joined by an edge. Its size is written \(\alpha(G)\).

Minimum clique cover: a cover of all the vertices by the fewest cliques. The number of cliques used is written \(\kappa(G)\).

Chord: an edge that joins two non-adjacent vertices of a cycle.

Chordal graph: a graph in which every cycle of length greater than \(3\) has a chord.

Lemma 1: \(\omega(G)\le \chi(G)\), that is, the clique number is at most the chromatic number.

Proof: Coloring the subgraph induced by a maximum clique alone already needs at least \(\omega(G)\) colors.

Lemma 2: \(\alpha(G)\le \kappa(G)\), that is, the size of a maximum independent set is at most the size of a minimum clique cover.

Proof: An independent set contains at most one vertex of each clique.

Lemma 3: Every induced subgraph of a chordal graph is chordal.

Proof: If some induced subgraph of a chordal graph is not chordal, it contains a chordless cycle of length greater than \(3\). Then the original graph cannot be chordal, whatever the rest of it looks like (however edges are added), a contradiction.

Lemma 4: No induced subgraph of a chordal graph is a cycle with more than \(3\) vertices.

Proof: A cycle with more than \(3\) vertices is not a chordal graph, so the previous lemma applies.

Recognizing chordal graphs

Problem statement

Given an undirected graph, decide whether it is chordal.

Vertex separators

For two vertices \(u,v\) of a graph \(G\), a vertex separator of the two is a set of vertices whose deletion disconnects \(u\) from \(v\). If no proper subset of a vertex separator of \(u\) and \(v\) is a vertex separator, it is called a minimal vertex separator.

Lemma 5: A minimal vertex separator of \(u,v\) splits the graph into several connected components. Let \(V_1\) be the component that contains \(u\) and \(V_2\) the one that contains \(v\). Then for every vertex \(a\) of the separator, \(N(a)\) contains a vertex of \(V_1\) and a vertex of \(V_2\).

Proof: If \(N(a)\) contains vertices of at most one of the components \(V_1\) and \(V_2\), then the graph stays disconnected when \(a\) is removed from the separator, so the separator was not minimal.

Lemma 6: In a chordal graph, the subgraph induced by a minimal vertex separator of any two vertices is a clique.

Proof: If the minimal vertex separator has size \(\le 1\), the induced subgraph is certainly a clique.

Otherwise, let \(x,y\) be two vertices of the separator. By Lemma 5, \(N(x)\) contains a vertex of \(V_1\) and a vertex of \(V_2\); call them \(x_1,x_2\). Define \(y_1,y_2\) in the same way. Note that \(x_1=y_1,x_2=y_2\) is possible.

Since \(V_1,V_2\) are connected components, each of the pairs \(x_1,y_1\) and \(x_2,y_2\) is joined by a shortest path. Let the shortest paths between \(x,y\) through the inside of \(V_1\) and of \(V_2\) be \(x-x_1\sim y_1-y,x-x_2\sim y_2-y\). Then the graph contains the cycle \(x-x_1\sim y_1-y-y_2\sim x_2-x\). Its length is \(\ge 4\), so by the definition of a chordal graph it has a chord.

If the chord joined the two components \(V_1\) and \(V_2\), the vertex set would not be a separator. If it joined two vertices inside one component, or a vertex inside a component and a vertex of the separator, the paths would not be shortest. So the chord can only join \(x\) and \(y\).

Hence any two vertices of a minimal vertex separator of a chordal graph are joined by an edge, which proves the claim.

Simplicial vertices

Let \(N(x)\) be the set of vertices adjacent to \(x\). If the subgraph induced by \(\{x\}+N(x)\) is a clique, \(x\) is called a simplicial vertex.

Lemma 7: Every chordal graph has at least one simplicial vertex, and a chordal graph that is not complete has at least two non-adjacent simplicial vertices.

Proof: By mathematical induction. Consider each connected component separately.

Base case: if the graph is isomorphic to a complete graph, every vertex is simplicial. If the graph has \(\le 3\) vertices, the lemma holds.

If the graph has \(\ge 4\) vertices and is not complete, there are \(u,v\) with \((u,v)\notin E\). Let \(I\) be a minimal vertex separator of \(u,v\), and let \(A,B\) be the connected components that contain \(u\) and \(v\) in the subgraph induced after deleting \(I\). By symmetry we only look at the side of \(A\). Let \(L=A+I\). If \(L\) is complete, \(u\) is a simplicial vertex. If not, \(L\) is an induced subgraph of the original graph and hence chordal, so it has two non-adjacent simplicial vertices; \(I\) is a clique, so any two of its vertices are adjacent, and therefore \(A\) contains a simplicial vertex. This vertex is still simplicial in the whole graph.

Each step of the proof splits the whole graph into several connected components, so the size strictly decreases and the pieces all satisfy the property. The induction therefore goes through.

Perfect elimination ordering

Let \(n=|V|\). A perfect elimination ordering \(v_1,v_2,\ldots ,v_n\) is a permutation of \(1,2,\ldots ,n\) such that \(v_i\) is a simplicial vertex of the subgraph induced by \(\{v_i,v_{i+1},\ldots ,v_n\}\).

Lemma 8: An undirected graph is chordal if and only if it has a perfect elimination ordering.

Necessity: A chordal graph with \(1\) vertex has a perfect elimination ordering. By Lemma 3 and Lemma 7, a perfect elimination ordering of a chordal graph with \(n\) vertices is obtained by adding a simplicial vertex to a perfect elimination ordering of a chordal graph with \(n-1\) vertices.

Sufficiency: Suppose an undirected graph has a perfect elimination ordering and contains a cycle with \(>3\) vertices. Let \(v\) be the vertex of the cycle that appears first in the ordering, and let \(v_1,v_2\) be its neighbors on the cycle. By the defining property of a perfect elimination ordering, that is, by the definition of a simplicial vertex, \(v_1,v_2\) are joined by an edge, a contradiction.

Naive algorithm

Repeatedly find a simplicial vertex \(v\) and append it to the perfect elimination ordering.

Delete \(v\) and its incident edges from the graph.

Repeat these steps. If every vertex gets deleted, the original graph is chordal and we have a perfect elimination ordering; if at some point the graph has no simplicial vertex, the original graph is not chordal.

This takes \(O(n^4)\) time.

MCS algorithm

Maximum cardinality search (MCS) finds a perfect elimination ordering of an undirected graph in \(O(n+m)\) time.

It numbers the vertices in reverse order, that is, it assigns the numbers from \(n\) down to \(1\).

Let \(label_x\) be the number of already numbered vertices adjacent to vertex \(x\). Each step numbers an unnumbered vertex whose \(label\) is largest.

For each \(i\), a linked list holds the vertices \(x\) with \(label_x=i\).

Each edge contributes at most \(2\) to \(\sum_{i=1}^n label_i\), so the algorithm runs in \(O(n+m)\).

Proof of correctness:

Let \(\alpha(x)\) be the position of \(x\) in this ordering. We have to prove that for every chordal graph the ordering produced by the algorithm is a perfect elimination ordering, that is, that the vertices which come after a given vertex in the ordering and are adjacent to it are pairwise adjacent.

Lemma 9: Consider three vertices \(u,v,w\) with \(\alpha(u)<\alpha(v)<\alpha(w)\). If \(uw\) is an edge and \(vw\) is not, then \(w\) contributes to the \(label\) of \(u\) but not to that of \(v\). For \(v\) to enter the ordering before \(u\), there must be an \(x\) with \(\alpha(v)<\alpha(x)\) such that \(vx\) is an edge and \(ux\) is not, that is, an \(x\) that contributes to \(v\) but not to \(u\).

Lemma 10: A chordal graph has no sequence \(v_0,v_1,\dots,v_k(k\ge 2)\) with the following properties:

  1. \(v_iv_j\) is an edge if and only if \(|i-j|=1\).
  2. \(\alpha(v_0)>\alpha(v_i)(i\in[1,k])\).
  3. There is an \(i\in[1,k-1]\) such that \(\alpha(v_i)<\alpha(v_{i+1})<\dots<\alpha(v_k)\) and \(\alpha(v_i)<\alpha(v_{i-1})<\dots<\alpha(v_1)<\alpha(v_k)<\alpha(v_0)\).

Proof:

We have \(\alpha(v_1)<\alpha(v_k)<\alpha(v_0)\), and \(v_1v_0\) is an edge while \(v_kv_0\) is not. So by Lemma 9 there is an \(x\) with \(\alpha(v_k)<\alpha(x)\) such that \(v_kx\) is an edge and \(v_1x\) is not.

Take the smallest \(j\in(1,k]\) for which \(v_jx\) is an edge. Then \(v_0x\) is not an edge, since otherwise \(v_0v_1\cdots v_jx\) would be a chordless cycle of length \(\ge 4\).

If \(x<v_0\), then \(v_0,v_1,\dots,v_j,x\) is again a sequence with these properties; if \(v_0<x\), then \(x,v_j,\dots,v_1,v_0\) is.

This derivation has increased \(\min(v_0,v_k)\), so repeating it must eventually produce a contradiction.

Theorem 1: For every chordal graph, the ordering produced by maximum cardinality search is a perfect elimination ordering.

Proof: Take any three vertices \(u,v,w\) with \(\alpha(u)<\alpha(v)<\alpha(w)\). We have to prove that if \(uv\) and \(uw\) are edges, then so is \(vw\).

We use proof by contradiction. Suppose it is not. Then \(w,u,v\) is a sequence with the properties of Lemma 10, and we have proved that no such sequence exists. This contradiction shows that \(vw\) is an edge.

Reference implementation
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
using namespace std;

int n;
vector<vector<int>> G;
vector<int> p, rnk;

void mcs() {
  vector<int> head(n, 0), prev(n + 1), next(n + 1), label(n + 1, 0);
  p.assign(n + 1, 0);
  rnk.assign(n + 1, 0);
  auto insert = [&](int v) {
    prev[v] = 0;
    next[v] = head[label[v]];
    if (next[v]) prev[next[v]] = v;
    head[label[v]] = v;
  };
  auto erase = [&](int v) {
    if (prev[v])
      next[prev[v]] = next[v];
    else
      head[label[v]] = next[v];
    if (next[v]) prev[next[v]] = prev[v];
  };
  for (int v = 1; v <= n; v++) insert(v);
  int largest = 0;
  for (int i = n; i >= 1; i--) {
    while (!head[largest]) largest--;
    int v = head[largest];
    erase(v);
    p[i] = v;
    rnk[v] = i;
    for (int u : G[v]) {
      if (rnk[u]) continue;
      erase(u);
      label[u]++;
      insert(u);
      largest = max(largest, label[u]);
    }
  }
}

If the graph is chordal, the ordering just computed is a perfect elimination ordering. But the graph may not be chordal, and then the ordering is certainly not a perfect elimination ordering. So the problem becomes checking whether the computed ordering is a perfect elimination ordering of the graph.

Checking whether an ordering is a perfect elimination ordering

Naive algorithm

Follow the definition: for each \(v_i\) of the ordering \(v\) in turn, check whether the vertices of \(\{v_i,v_{i+1},\ldots ,v_n\}\) adjacent to \(v_i\) form a clique. This takes \(O(nm)\) time.

Optimized algorithm

Let \(N^+(u)\) be the set of vertices that come after \(u\) in the ordering and are adjacent to \(u\), and let \(f(u)\) be the earliest of them in the ordering. For each vertex \(u\) with nonempty \(N^+(u)\), it is enough to check that every vertex of \(N^+(u)\setminus\{f(u)\}\) is adjacent to \(f(u)\).

This condition is clearly necessary. Sufficiency follows by induction over the ordering from back to front: if all later vertices meet the requirement of a perfect elimination ordering, then \(N^+(f(u))\) is a clique. When the check passes, \(N^+(u)\setminus\{f(u)\}\subseteq N^+(f(u))\) and all of these vertices are adjacent to \(f(u)\), so \(N^+(u)\) is a clique as well. Nothing has to be checked when \(N^+(u)\) is empty.

First scan the adjacency lists to find \(f(u)\) for every vertex, and put the vertices with the same \(f(u)\) into one group. To process the group with \(f(u)=v\), mark all neighbors of \(v\), then scan the adjacency list of each vertex \(u\) of the group and check that all its neighbors that come after \(v\) in the ordering are marked. With the vertex number \(v\) as the mark value, the mark array does not have to be cleared after each group. Every vertex belongs to at most one group, and its adjacency list is scanned at most once each for computing \(f(u)\), for setting marks and for checking, so the total time is \(O(n+m)\).

Reference implementation
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
using namespace std;

int n;
vector<vector<int>> G;
vector<int> p, rnk;

int fail_u, fail_v, fail_w;

bool check() {
  vector<vector<int>> bucket(n + 1);
  vector<int> mark(n + 1, 0);
  for (int i = 1; i <= n; i++) {
    int u = p[i], first = 0;
    for (int v : G[u]) {
      if (rnk[v] > rnk[u] && (!first || rnk[v] < rnk[first])) first = v;
    }
    if (first) bucket[first].push_back(u);
  }

  fail_u = 0;
  for (int v = 1; v <= n; v++) {
    // one marking pass per group; mark[w] == v: w is adjacent to the current v
    for (int w : G[v]) mark[w] = v;
    for (int u : bucket[v]) {
      for (int w : G[u]) {
        if (rnk[w] > rnk[v] && mark[w] != v) {
          // record the last failing vertex of the ordering and its two neighbors
          if (!fail_u || rnk[u] > rnk[fail_u]) {
            fail_u = u;
            fail_v = v;
            fail_w = w;
          }
          break;
        }
      }
    }
  }
  return !fail_u;
}

This solves the chordal graph recognition problem in \(O(n+m)\) time.

Maximal cliques of a chordal graph

Let \(N(x)\) be the sequence of vertices that are joined to \(x\) by an edge and come after \(x\) in the perfect elimination ordering. Then every maximal clique of a chordal graph is of the form \(\{x\}+N(x)\).

Proof: Take a maximal clique \(V\) of a chordal graph, and let \(x\) be the first of its vertices in the perfect elimination ordering. Then \(V\subseteq \{x\}+N(x)\), and since \(V\) is a maximal clique, \(V=\{x\}+N(x)\).

A chordal graph has at most \(n\) maximal cliques. To find them all, decide for each \(\{x\}+N(x)\) whether it is a maximal clique.

Let \(A=\{x\}+N(x),B=\{y\}+N(y)\). If \(A\subsetneqq B\), then \(A\) is not a maximal clique. Clearly \(y\) then comes before \(x\) in the perfect elimination ordering.

Let \(nxt_x\) be the earliest vertex of \(N(x)\) in the perfect elimination ordering, and let \(y*\) be the latest of all \(y\) with \(A\subseteq B\). Then \(nxt_{y*}=x\) must hold: otherwise \(y*\) is not the latest, because setting \(y*=nxt_{y*}\) still satisfies the condition.

\(A\subsetneqq B\) if and only if \(|A|+1\le |B|\).

The problem thus reduces to deciding whether there is a \(y\) with \(nxt_y=x\) and \(|N(x)|+1\le |N(y)|\). This takes \(O(n+m)\) time.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
for (int i = 1; i <= n; i++) {
  cur = 0;
  for (vector<int>::iterator it = G[p[i]].begin(); it != G[p[i]].end(); it++)
    if (rnk[p[i]] < rnk[*it]) {
      s[++cur] = *it;
      if (rnk[s[cur]] < rnk[s[1]]) swap(s[1], s[cur]);
    }
  fst[p[i]] = s[1];
  N[p[i]] = cur;
}
for (int i = 1; i <= n; i++) {
  if (!vis[p[i]]) ans++;
  if (N[p[i]] >= N[fst[p[i]]] + 1) vis[fst[p[i]]] = true;
}

Chromatic number and clique number of a chordal graph

A construction: color the vertices one by one, going through the perfect elimination ordering from back to front, and give each vertex the smallest color it can take. This takes \(O(m+n)\) time.

Proof of correctness: Suppose this method uses \(t\) colors; then \(t\ge \chi(G)\). The vertices of a clique all get different colors, so \(t=\omega(G)\), and by Lemma 1, \(t=\omega(G)\le \chi(G)\). Together these give \(t=\chi(G)=\omega(G)\).

If you need only the chromatic number or the clique number of a chordal graph and not the coloring itself, take the maximum of \(|\{x\}+N(x)|\).

1
for (int i = 1; i <= n; i++) ans = max(ans, deg[i] + 1);

Maximum independent set and minimum clique cover of a chordal graph

Maximum independent set: go through the perfect elimination ordering from front to back and select every vertex that has no edge to a vertex already selected.

Minimum clique cover: if the maximum independent set is \(\{v_1,v_2,\ldots ,v_t\}\), then the set of cliques \(\{\{v_1+N(v_1)\},\{v_2+N(v_2)\},\ldots ,\{v_t+N(v_t)\} \}\) is a minimum clique cover of the graph. Both take \(O(n+m)\) time.

Proof of correctness: Let \(t\) be the size of the independent set and of the clique cover constructed above. By definition \(t\le \alpha(G),t\ge \kappa(G)\), and by Lemma 2, \(\alpha(G)\le \kappa(G)\), so \(t=\alpha(G)=\kappa(G)\).

1
2
3
4
5
6
for (int i = 1; i <= n; i++)
  if (!vis[p[i]]) {
    ans++;
    for (vector<int>::iterator it = G[p[i]].begin(); it != G[p[i]].end(); it++)
      vis[*it] = true;
  }

Practice problems

Library Checker - Chordal Graph Recognition

SPOJ FISHNET - Fishing Net

P3196 [HNOI2008] The Magical Kingdom

P3852 [TJOI2007] Children

References

Notes on Chordal Graphs (in Chinese)

WC 2009 lecture slides (in Chinese)

A Summary of Chordal Graphs - zhoushuyu (in Chinese)

R. E. Tarjan and M. Yannakakis, Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs, SIAM J. Comput., 13 (1984), pp. 566–579.