AIOJ

A chordal graph is a special kind of graph. Many NP-hard problems 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 those of the original graph.

Induced subgraph: A graph whose vertex set is a subset of the original vertex set, and whose edge set contains every edge whose two endpoints both belong to the selected 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 in a maximum clique, denoted by $\omega(G)$ .

Minimum coloring: Coloring vertices with as few colors as possible so that the endpoints of every edge have different colors.

Chromatic number: The number of colors in a minimum coloring, denoted by $\chi(G)$ .

Maximum independent set: The largest vertex set in which no two vertices are directly connected by an edge. Its size is denoted by $\alpha(G)$ .

Minimum clique cover: Covering all vertices with as few cliques as possible. The number of cliques used is denoted by $\kappa(G)$ .

Chord: An edge connecting two nonadjacent vertices on a cycle.

Chordal graph: A graph in which every cycle of length greater than $3$ has a chord.

Lemma 1: Clique number $\omega(G)\le \chi(G)$ chromatic number.

Proof: Consider coloring the induced subgraph of a maximum clique alone. At least $\omega(G)$ colors are required.

Lemma 2: Maximum independent-set size $\alpha(G)\le \kappa(G)$ minimum clique-cover size.

Proof: At most one vertex can be selected from each clique.

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

Proof: If a chordal graph had an induced subgraph that was not chordal, that induced subgraph would contain a chordless cycle of length greater than $3$ . No matter how edges are added to the original graph, this would not make the original graph chordal, a contradiction.

Lemma 4: No induced subgraph of a chordal graph can be a cycle with more than $3$ vertices.

Proof: A cycle with more than $3$ vertices is not chordal, so the result follows from the preceding lemma.

Recognizing chordal graphs

Problem statement

Given an undirected graph, determine whether it is chordal.

Vertex separators

In a graph $G$ , for two vertices $u,v$ , define a vertex separator between them as a set whose deletion leaves $u,v$ disconnected. If no proper subset of a vertex separator between $u,v$ is also a vertex separator, call it a minimal vertex separator.

Lemma 5: A minimal vertex separator for $u,v$ divides the original graph into several connected components. Let $V_1$ be the component containing $u$ and $V_2$ the component containing $v$ . For every vertex $a$ in the minimal vertex separator, $N(a)$ contains vertices from both $V_1$ and $V_2$ .

Proof: If $N(a)$ contained vertices from at most one of $V_1$ and $V_2$ , deleting $a$ from the vertex separator would still leave the two vertices disconnected, so the original separator would not be minimal.

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

Proof: If the minimal vertex separator has size $\le 1$ , its induced subgraph is clearly a clique.

Otherwise, let two vertices in the minimal vertex separator be $x,y$ . By Lemma 5, $N(x)$ contains vertices from $V_1,V_2$ , say $x_1,x_2$ ; likewise, let them be $y_1,y_2$ . Note that it is possible that $x_1=y_1,x_2=y_2$ .

Since $V_1,V_2$ are connected components, there are shortest paths between $x_1,y_1$ and between $x_2,y_2$ . Let $x,y$ be the two separator vertices, and let the shortest paths through the interiors of $V_1,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$ , whose length is $\ge 4$ . By the definition of a chordal graph, this cycle has a chord.

If the chord connects the two components $V_1,V_2$ , the vertex set is not a vertex separator. If it connects two vertices inside one component, or a vertex inside one component with a vertex in the vertex separator, it contradicts the shortest-path property. Therefore the chord can only connect $x,y$ .

Thus, every two vertices in a minimal vertex separator of a chordal graph are directly connected by an edge, proving the lemma.

Simplicial vertices

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

Lemma 7: Every chordal graph has at least one simplicial vertex; a chordal graph that is not complete has at least two nonadjacent simplicial vertices.

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

Induction base: If the graph is isomorphic to a complete graph, every vertex is simplicial. If the graph has at most $\le 3$ vertices, the lemma holds.

If the graph has $\ge 4$ vertices and is not complete, there must be $u,v$ with $(u,v)\notin E$ . Let $I$ be a minimal vertex separator between $u,v$ . Let $A,B$ be the connected components containing $u,v$ in the induced subgraph obtained after deleting $I$ . By symmetry, consider only the side containing $A$ , and let $L=A+I$ . If $L$ is complete, then $u$ is simplicial. Otherwise, since $L$ is an induced subgraph of the original graph, it is chordal, so it has two nonadjacent simplicial vertices. Since $I$ is a clique, its vertices are pairwise adjacent, so at least one of those simplicial vertices lies in $A$ . That simplicial vertex remains simplicial when extended to the whole graph.

Since each step divides the whole graph into connected components of strictly smaller size, all of which satisfy the property, the induction is complete.

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 simplicial in the induced subgraph on $\{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.

Sufficiency: 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 can be obtained by taking a perfect elimination ordering of a chordal graph with $n-1$ vertices and appending a simplicial vertex.

Necessity: Suppose an undirected graph has a cycle with $>3$ vertices and has a perfect elimination ordering. Let $v$ be the first vertex of the cycle to appear in the ordering, and suppose the first vertex is $v$ and its two neighbors on the cycle are $v_1,v_2$ . The definition of a simplicial vertex and the property of a perfect elimination ordering imply that $v_1,v_2$ are directly connected, a contradiction.

Naive algorithm

Each time, find a simplicial vertex $v$ and add it to the perfect elimination ordering.

Delete vertex $v$ and all edges incident to it from the graph.

Repeat the process. If every vertex is deleted, the original graph is chordal and a perfect elimination ordering has been found; if the graph has no simplicial vertex, the original graph is not chordal.

The time complexity is $O(n^4)$ .

MCS algorithm

Maximum Cardinality Search is an algorithm that finds a perfect elimination ordering of an undirected graph in $O(n+m)$ time.

Number the vertices in reverse order, that is, from $n$ down to $1$ .

Let $label_x$ denote the number of already numbered vertices adjacent to vertex $x$ . At each step, number the unnumbered vertex with the largest $label$ .

Use linked lists to maintain, for each $i$ , the vertices $x$ satisfying $label_x=i$ .

Since every edge contributes at most $2$ to $\sum_{i=1}^n label_i$ , the time complexity is $O(n+m)$ .

Correctness proof:

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

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

Lemma 10: A chordal graph cannot contain a sequence $v_0,v_1,\dots,v_k(k\ge 2)$ satisfying all of the following:

$v_iv_j$ is an edge if and only if $|i-j|=1$ .
$\alpha(v_0)>\alpha(v_i)(i\in[1,k])$ .
There exists $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:

Since $\alpha(v_1)<\alpha(v_k)<\alpha(v_0)$ , $v_1v_0$ is an edge, and $v_kv_0$ is not, property 1 implies that there is an $x$ with $\alpha(v_k)<\alpha(x)$ such that $v_kx$ is an edge but $v_1x$ is not.

Let $j\in(1,k]$ be the smallest index for which $v_jx$ is an edge. We can conclude that $v_0x$ is not an edge; otherwise $v_0v_1\cdots v_jx$ would form a chordless cycle of length $\ge 4$ .

If $x<v_0$ , then $v_0,v_1,\dots,v_j,x$ is another sequence satisfying the properties. If $v_0<x$ , then $x,v_j,\dots,v_1,v_0$ is such a sequence.

In this derivation, we increased $\min(v_0,v_k)$ . Continuing in this way must eventually produce a contradiction.

Theorem 1: For every chordal graph, the ordering produced by Maximum Cardinality Search is a perfect elimination ordering.

Proof: Consider any three vertices $u,v,w$ with $\alpha(u)<\alpha(v)<\alpha(w)$ . We need to prove that if $uv$ and $uw$ are edges, then $vw$ is also an edge.

Suppose otherwise. Then $w,u,v$ form a sequence satisfying the properties in Lemma 10, but we have proved that no such sequence exists, a contradiction. Therefore $vw$ is an edge.

Reference code:

while (cur) {
  p[cur] = h[nww];
  rnk[p[cur]] = cur;
  h[nww] = nxt[h[nww]];
  lst[h[nww]] = 0;
  lst[p[cur]] = nxt[p[cur]] = 0;
  tf[p[cur]] = true;
  for (vector<int>::iterator it = G[p[cur]].begin(); it != G[p[cur]].end();
       it++)
    if (!tf[*it]) {
      if (h[deg[*it]] == *it) h[deg[*it]] = nxt[*it];
      nxt[lst[*it]] = nxt[*it];
      lst[nxt[*it]] = lst[*it];
      lst[*it] = nxt[*it] = 0;
      deg[*it]++;
      nxt[*it] = h[deg[*it]];
      lst[h[deg[*it]]] = *it;
      h[deg[*it]] = *it;
    }
  cur--;
  if (h[nww + 1]) nww++;
  while (nww && !h[nww]) nww--;
}

If the original graph is chordal, the result at this point is a perfect elimination ordering. However, since the original graph may not be chordal, the result is then certainly not a perfect elimination ordering. The problem is therefore reduced to checking whether the computed ordering is a perfect elimination ordering of the original graph.

Checking whether an ordering is a perfect elimination ordering

Naive algorithm

By definition, in the perfect elimination ordering $v$ , check whether the vertices in $\{v_i,v_{i+1},\ldots ,v_n\}$ adjacent to $v_i$ form a clique. The time complexity is $O(nm)$ .

Optimized algorithm

By the definition of a perfect elimination ordering, let the vertices adjacent to $v_i$ in ${v_i,v_{i+1},\ldots , v_n}$ , in increasing order, be $\{v_{c_1},v_{c_2},\ldots ,v_{c_k} \}$ . It is enough to check whether $v_{c_1}$ is directly connected to every other vertex. The time complexity is $O(n+m)$ .

jud = true;
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]);
    }
  for (int j = 2; j <= cur; j++)
    if (!st[s[1]].count(s[j])) {
      jud = false;
      break;
    }
}
if (!jud)
  printf("Imperfect\n");
else
  printf("Perfect\n");

Thus, the chordal graph recognition problem can be solved in $O(n+m)$ time.

Maximal cliques of chordal graphs

Let $N(x)$ be the sequence of vertices directly adjacent to $x$ that occur after $x$ in the perfect elimination ordering. Every maximal clique of a chordal graph is of the form $\{x\}+N(x)$ .

Proof: Consider a maximal clique $V$ of a chordal graph, and let $x$ be the first vertex in the clique to appear in the perfect elimination ordering. Then $V\subseteq \{x\}+N(x)$ . Since $V$ is maximal, $V=\{x\}+N(x)$ .

A chordal graph has at most $n$ maximal cliques. To find all maximal cliques, we can determine whether each $\{x\}+N(x)$ is maximal.

Let $A=\{x\}+N(x),B=\{y\}+N(y)$ . If $A\subsetneqq B$ , then $A$ is not maximal. In this case, $y$ clearly appears before $x$ in the perfect elimination ordering.

Let $nxt_x$ be the earliest vertex in $N(x)$ in the perfect elimination ordering, and let $y*$ be the latest among all $y$ satisfying $A\subseteq B$ . Then necessarily $nxt_{y*}=x$ ; otherwise replacing it by $y*=nxt_{y*}$ would still satisfy the condition, so the chosen $y*$ would not be the latest.

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

The problem is reduced to checking whether there exists a $y$ satisfying $nxt_y=x$ and $|N(x)|+1\le |N(y)|$ . The time complexity is $O(n+m)$ .

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 and clique numbers of chordal graphs

One construction method is to color the vertices one by one in reverse perfect elimination order, assigning each vertex the smallest available color. The time complexity is $O(m+n)$ .

Correctness proof: If this method uses $t$ colors, then $t\ge \chi(G)$ . Every vertex in a clique has a different color, so $t=\omega(G)$ . By Lemma 1, $t=\omega(G)\le \chi(G)$ . Therefore $t=\chi(G)=\omega(G)$ .

If only the chromatic/clique number is needed, without constructing a coloring, take the maximum of $|\{x\}+N(x)|$ .

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

Maximum independent set and minimum clique cover of chordal graphs

Maximum independent set: Traverse the perfect elimination ordering from beginning to end, selecting every vertex that has no edge to any previously selected vertex.

Minimum clique cover: Let the maximum independent set be $\{v_1,v_2,\ldots ,v_t\}$ . Then the collection 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 procedures have time complexity $O(n+m)$ .

Correctness proof: Let the independent-set size and clique-cover size produced above be $t$ . By definition, $t\le \alpha(G),t\ge \kappa(G)$ . By Lemma 2, $\alpha(G)\le \kappa(G)$ , so $t=\alpha(G)=\kappa(G)$ .

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;
  }