Chordal Graph
A chord graph is a special type of graph. Many NP-Hard problems on general graphs have excellent linear-time algorithms on chord graphs.
Some Definitions and Properties
Subgraph: A graph whose vertex set and edge set are subsets of the original graph's vertex set and edge set.
Induced subgraph: A graph whose vertex set is a subset of the original graph's vertex set, and whose edge set consists of all edges whose both endpoints are in the selected vertex set.
Clique: A complete subgraph.
Maximal clique: A clique that is not a subgraph of any other clique.
Maximum clique: The clique with the largest number of vertices.
Clique number: The number of vertices in the maximum clique, denoted as \(\omega(G)\).
Minimum coloring: Coloring the vertices with the fewest colors such that any two vertices connected by an edge have different colors.
Chromatic number: The number of colors used in a minimum coloring, denoted as \(\chi(G)\).
Maximum independent set: The largest vertex set such that no two vertices in the set are directly connected by an edge. The size of this set is denoted as \(\alpha(G)\).
Minimum clique cover: Covering all vertices with the fewest cliques. The number of cliques used is denoted as \(\kappa(G)\).
Chord: An edge connecting two non-adjacent vertices in a cycle.
Chord 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 the maximum clique alone; at least \(\omega(G)\) colors are needed.
Lemma 2: Maximum independent set size \(\alpha(G)\le \kappa(G)\) minimum clique cover number.
Proof: At most one vertex can be selected from each clique.
Lemma 3: Any induced subgraph of a chord graph must be a chord graph.
Proof: If a chord graph has an induced subgraph that is not a chord graph, it means there exists a cycle of length greater than \(3\) without a chord in this induced subgraph. Then, no matter how the original graph is modified (by adding edges), it cannot become a chord graph, which is a contradiction.
Lemma 4: Any induced subgraph of a chord graph cannot be a cycle with more than \(3\) vertices.
Proof: A cycle with more than \(3\) vertices is not a chord graph, as per the above theorem.
Determining Chord Graphs
Problem Description
Given an undirected graph, determine whether it is a chord graph.
Vertex Cut Set
For two vertices \(u,v\) in graph \(G\), define the vertex cut set between them as a set of vertices whose removal disconnects \(u\) and \(v\). If no proper subset of a vertex cut set between \(u\) and \(v\) is a vertex cut set, it is called a minimal vertex cut set.
Lemma 5: The minimal vertex cut set between \(u\) and \(v\) divides the original graph into several connected components. Let the component containing \(u\) be \(V_1\) and the component containing \(v\) be \(V_2\). Then, for any vertex \(a\) in the minimal vertex cut set, \(N(a)\) must contain vertices from both \(V_1\) and \(V_2\).
Proof: If \(N(a)\) contains vertices from at most one of \(V_1\) or \(V_2\), removing \(a\) from the vertex cut set would still leave the graph disconnected, meaning the original vertex cut set was not minimal.
Lemma 6: The induced subgraph of any minimal vertex cut set between two vertices in a chord graph must be a clique.
Proof: When the size of the minimal vertex cut set is \(\le 1\), the induced subgraph is trivially a clique.
Otherwise, let \(x,y\) be two vertices in the minimal vertex cut set. By Lemma 5, \(N(x)\) contains vertices from \(V_1\) and \(V_2\), say \(x_1,x_2\). Similarly, let \(y_1,y_2\) be such vertices for \(y\). Note that it is possible that \(x_1=y_1\) or \(x_2=y_2\).
Since \(V_1\) and \(V_2\) are connected components, there exist shortest paths between the pairs \((x_1,y_1)\) and \((x_2,y_2)\). Let the shortest paths inside \(V_1\) and \(V_2\) be \(x-x_1\sim y_1-y\) and \(x-x_2\sim y_2-y\), respectively. Then, there exists a cycle \(x-x_1\sim y_1-y-y_2\sim x_2-x\) in the graph, whose length must be \(\ge 4\). By the definition of chord graphs, this cycle must have a chord.
If this chord connects the two components \(V_1\) and \(V_2\), then the vertex set is not a vertex cut set. If the chord connects two vertices within a single component or connects a vertex inside a component to a vertex in the vertex cut set, it violates the property of shortest paths. Therefore, the chord must connect \(x\) and \(y\).
Thus, it is proven that any two vertices in a minimal vertex cut set of a chord graph are directly connected by an edge.
Simplicial Vertex
Let \(N(x)\) denote the set of vertices adjacent to \(x\). If the induced subgraph of the vertex set \(\{x\}+N(x)\) is a clique, then \(x\) is called a simplicial vertex.
Lemma 7: Every chord graph has at least one simplicial vertex. A chord graph that is not a complete graph has at least two non-adjacent simplicial vertices.
Proof: By mathematical induction, consider each connected component separately.
Induction base: When the graph is isomorphic to a complete graph, every vertex is simplicial. When the graph has \(\le 3\) vertices, the lemma holds.
If the graph has \(\ge 4\) vertices and is not a complete graph, there must exist \(u,v\) such that \((u,v)\notin E\). Let \(I\) be the minimal vertex cut set between \(u\) and \(v\). Let \(A\) and \(B\) be the connected components containing \(u\) and \(v\), respectively, after removing \(I\). Due to symmetry, we only consider the side of \(A\). Let \(L=A+I\). If \(L\) is a complete graph, then \(u\) is simplicial; otherwise, since \(L\) is an induced subgraph of the original graph, it must also be a chord graph, so it has two non-adjacent simplicial vertices. Because \(I\) is a clique where all vertices are adjacent, \(A\) must contain a simplicial vertex. This simplicial vertex remains simplicial in the original graph.
Since each step divides the graph into smaller connected components, the size decreases, and the property holds, the induction is valid.
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 in the induced subgraph of \(\{v_i,v_{i+1},\ldots ,v_n\}\).
Lemma 8: An undirected graph is a chord graph if and only if it has a perfect elimination ordering.
Sufficiency: A chord graph with \(1\) vertex has a perfect elimination ordering. By Lemma 3 and Lemma 7, the perfect elimination ordering for a chord graph with \(n\) vertices can be obtained by adding a simplicial vertex to the perfect elimination ordering of a chord graph with \(n-1\) vertices.
Necessity: Assume an undirected graph has a cycle with more than \(3\) vertices and also has a perfect elimination ordering. Let \(v\) be the first vertex in the cycle to appear in the perfect elimination ordering. Suppose \(v\) is connected to \(v_1\) and \(v_2\) in the cycle. Then, by the properties of the perfect elimination ordering and the definition of a simplicial vertex, \(v_1\) and \(v_2\) must be directly connected by an edge, which is a contradiction.
Naive Algorithm
Repeatedly find a simplicial vertex \(v\) and add it to the perfect elimination ordering.
Remove vertex \(v\) and all edges incident to it from the graph.
Repeat the above process. If all vertices are removed, the original graph is a chord graph and a perfect elimination ordering is obtained. If no simplicial vertex exists at any step, the original graph is not a chord graph.
Time complexity: \(O(n^4)\).
MCS Algorithm
Maximum Cardinality Search is an algorithm that can find a perfect elimination ordering of an undirected graph in \(O(n+m)\) time.
Label vertices in reverse order, i.e., assign labels from \(n\) to \(1\).
Let \(label_x\) denote the number of already labeled vertices adjacent to \(x\). At each step, choose the unlabeled vertex with the largest \(label\) value to label.
Use linked lists to maintain, for each \(i\), the vertices \(x\) satisfying \(label_x=i\).
Since each edge contributes at most \(2\) to \(\sum_{i=1}^n label_i\), the time complexity is \(O(n+m)\).
Proof of Correctness:
Let \(\alpha(x)\) be the position of \(x\) in the ordering. We need to prove that for any chord graph, the sequence produced by the algorithm is a perfect elimination ordering, i.e., for any vertex, all vertices that come after it in the sequence 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\) are adjacent but \(vw\) are not, then \(w\) contributes to the \(label\) of \(u\) but not to \(v\). For \(v\) to be added to the sequence before \(u\), there must exist a vertex \(x\) with \(\alpha(v)<\alpha(x)\) such that \(vx\) are adjacent but \(ux\) are not, i.e., \(x\) contributes to \(v\) but not to \(u\).
Lemma 10: Any chord graph cannot have a sequence \(v_0,v_1,\dots,v_k(k\ge 2)\) satisfying the following properties:
- \(v_iv_j\) are adjacent 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)\), and \(v_1v_0\) are adjacent while \(v_kv_0\) are not, by property 1, there exists \(x\) such that \(\alpha(v_k)<\alpha(x)\) and \(v_kx\) are adjacent, but \(v_1x\) are not.
Consider the smallest \(j\in(1,k]\) such that \(v_jx\) are adjacent. We can deduce that \(v_0x\) are not adjacent; otherwise, \(v_0v_1\cdots v_jx\) forms a cycle of length \(\ge 4\) without a chord.
If \(x<v_0\), then \(v_0,v_1,\dots,v_j,x\) is also a sequence satisfying the properties; if \(v_0<x\), then \(x,v_j,\dots,v_1,v_0\) is also such a sequence.
In the above derivation, we increased \(\min(v_0,v_k)\). Continuing this process will eventually lead to a contradiction.
Theorem 1: For any chord graph, the sequence produced by the Maximum Cardinality Search algorithm 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\) are adjacent and \(uw\) are adjacent, then \(vw\) must be adjacent.
Assume for contradiction that \(vw\) are not adjacent. Then \(w,u,v\) form a sequence satisfying the properties in Lemma 10. We have proven that such a sequence cannot exist, so we have a contradiction, and \(vw\) must be adjacent.
Reference code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | |
If the original graph is a chord graph, the sequence obtained is a perfect elimination ordering. However, since the original graph might not be a chord graph, the sequence obtained might not be a perfect elimination ordering. Thus, the problem reduces to determining whether the obtained sequence is a perfect elimination ordering of the original graph.
Determining Whether a Sequence is a Perfect Elimination Ordering
Naive Algorithm
According to the definition, sequentially check whether the vertices adjacent to \(v_i\) in \(\{v_i,v_{i+1},\ldots ,v_n\}\) form a clique. Time complexity: \(O(nm)\).
Optimized Algorithm
According to the definition of a perfect elimination ordering, let the vertices adjacent to \(v_i\) in \({v_i,v_{i+1},\ldots , v_n}\) sorted in increasing order be \(\{v_{c_1},v_{c_2},\ldots ,v_{c_k} \}\). Then it suffices to check whether \(v_{c_1}\) is directly connected to all other vertices. Time complexity: \(O(n+m)\).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | |
Thus, the chord graph determination problem can be solved in \(O(n+m)\) time.
Maximal Cliques of Chord Graphs
Let \(N(x)\) be the set of vertices that are adjacent to \(x\) and appear after \(x\) in the perfect elimination ordering. Then the maximal cliques of a chord graph are exactly \(\{x\}+N(x)\).
Proof: Consider a maximal clique \(V\) of a chord graph. Let \(x\) be the first vertex of \(V\) to appear in the perfect elimination ordering. Then \(V\subseteq \{x\}+N(x)\). Since \(V\) is a maximal clique, \(V=\{x\}+N(x)\).
A chord graph has at most \(n\) maximal cliques. To find all maximal cliques of a chord graph, we can check whether each \(\{x\}+N(x)\) is a maximal clique.
Let \(A=\{x\}+N(x), B=\{y\}+N(y)\). If \(A\subsetneqq B\), then \(A\) is not a maximal clique. In this case, \(y\) clearly appears before \(x\) in the perfect elimination ordering.
Let \(nxt_x\) denote the vertex in \(N(x)\) that appears earliest in the perfect elimination ordering, and let \(y*\) be the latest vertex among all \(y\) satisfying \(A\subseteq B\). Then it must hold that \(nxt_{y*}=x\); otherwise, \(y*\) is not the latest, and setting \(y*=nxt_{y*}\) would still satisfy the condition.
\(A\subsetneqq B\) if and only if \(|A|+1\le |B|\).
The problem reduces to checking whether there exists a \(y\) such that \(nxt_y=x\) and \(|N(x)|+1\le |N(y)|\). Time complexity: \(O(n+m)\).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | |
Chromatic Number / Clique Number of Chord Graphs
A construction method: Color the vertices from last to first according to the perfect elimination ordering, assigning each vertex the smallest available color. Time complexity: \(O(m+n)\).
Proof of correctness: Let the above method use \(t\) colors. Then \(t\ge \chi(G)\). Since all vertices in a clique must have different colors, \(t=\omega(G)\). By Lemma 1, \(t=\omega(G)\le \chi(G)\). Therefore, \(t=\chi(G)=\omega(G)\).
If only the chromatic number/clique number is needed without the coloring scheme, it can be obtained by taking the maximum value of \(|\{x\}+N(x)|\).
1 | |
Maximum Independent Set / Minimum Clique Cover of Chord Graphs
Maximum independent set: Traverse the perfect elimination ordering from front to back, selecting all vertices that are not adjacent to any already selected vertex.
Minimum clique cover: Let the maximum independent set be \(\{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 time complexities are \(O(n+m)\).
Proof of correctness: Let the independent set size and clique cover number obtained by the above method be \(t\). By definition, \(t\le \alpha(G)\) and \(t\ge \kappa(G)\). By Lemma 2, \(\alpha(G)\le \kappa(G)\). Therefore, \(t=\alpha(G)=\kappa(G)\).
1 2 3 4 5 6 | |
Exercises
References
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用