Hubbry Logo
Chordal graphChordal graphMain
Open search
Chordal graph
Community hub
Chordal graph
logo
8 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Chordal graph
Chordal graph
Chordal graph
View on Wikipedia
from Wikipedia
A cycle (black) with two chords (green). As for this part, the graph is chordal. However, removing one green edge would result in a non-chordal graph. Indeed, the other green edge with three black edges would form a cycle of length four with no chords.

In the mathematical area of graph theory, a chordal graph is one in which all cycles of four or more vertices have a chord, which is an edge that is not part of the cycle but connects two vertices of the cycle. Equivalently, every induced cycle in the graph should have exactly three vertices. The chordal graphs may also be characterized as the graphs that have perfect elimination orderings, as the graphs in which each minimal separator is a clique, and as the intersection graphs of subtrees of a tree. They are sometimes also called rigid circuit graphs[1] or triangulated graphs:[2] a chordal completion of a graph is typically called a triangulation of that graph.

Chordal graphs are a subset of the perfect graphs. They may be recognized in linear time, and several problems that are hard on other classes of graphs such as graph coloring may be solved in polynomial time when the input is chordal. The treewidth of an arbitrary graph may be characterized by the size of the cliques in the chordal graphs that contain it.

Perfect elimination and efficient recognition

[edit]

A perfect elimination ordering in a graph is an ordering of the vertices of the graph such that, for each vertex v, v and the neighbors of v that occur after v in the order form a clique. A graph is chordal if and only if it has a perfect elimination ordering.[3]

Rose, Lueker & Tarjan (1976) (see also Habib et al. 2000) show that a perfect elimination ordering of a chordal graph may be found efficiently using an algorithm known as lexicographic breadth-first search. This algorithm maintains a partition of the vertices of the graph into a sequence of sets; initially this sequence consists of a single set with all vertices. The algorithm repeatedly chooses a vertex v from the earliest set in the sequence that contains previously unchosen vertices, and splits each set S of the sequence into two smaller subsets, the first consisting of the neighbors of v in S and the second consisting of the non-neighbors. When this splitting process has been performed for all vertices, the sequence of sets has one vertex per set, in the reverse of a perfect elimination ordering.

Since both this lexicographic breadth first search process and the process of testing whether an ordering is a perfect elimination ordering can be performed in linear time, it is possible to recognize chordal graphs in linear time. The graph sandwich problem on chordal graphs is NP-complete[4] whereas the probe graph problem on chordal graphs has polynomial-time complexity.[5]

The set of all perfect elimination orderings of a chordal graph can be modeled as the basic words of an antimatroid; Chandran et al. (2003) use this connection to antimatroids as part of an algorithm for efficiently listing all perfect elimination orderings of a given chordal graph.

Maximal cliques and graph coloring

[edit]

Another application of perfect elimination orderings is finding a maximum clique of a chordal graph in polynomial-time, while the same problem for general graphs is NP-complete. More generally, a chordal graph can have only linearly many maximal cliques, while non-chordal graphs may have exponentially many. This implies that the class of chordal graphs has few cliques. To list all maximal cliques of a chordal graph, simply find a perfect elimination ordering, form a clique for each vertex v together with the neighbors of v that are later than v in the perfect elimination ordering, and test whether each of the resulting cliques is maximal.

The clique graphs of chordal graphs are the dually chordal graphs.[6]

The largest maximal clique is a maximum clique, and, as chordal graphs are perfect, the size of this clique equals the chromatic number of the chordal graph. Chordal graphs are perfectly orderable: an optimal coloring may be obtained by applying a greedy coloring algorithm to the vertices in the reverse of a perfect elimination ordering.[7]

The chromatic polynomial of a chordal graph is easy to compute. Find a perfect elimination ordering v1, v2, …, vn. Let Ni equal the number of neighbors of vi that come after vi in that ordering. For instance, Nn = 0. The chromatic polynomial equals (The last factor is simply x, so x divides the polynomial, as it should.) Clearly, this computation depends on chordality.[8]

Minimal separators

[edit]

In any graph, a vertex separator is a set of vertices the removal of which leaves the remaining graph disconnected; a separator is minimal if it has no proper subset that is also a separator. According to a theorem of Dirac (1961), chordal graphs are graphs in which each minimal separator is a clique; Dirac used this characterization to prove that chordal graphs are perfect.

The family of chordal graphs may be defined inductively as the graphs whose vertices can be divided into three nonempty subsets A, S, and B, such that ⁠⁠ and ⁠⁠ both form chordal induced subgraphs, S is a clique, and there are no edges from A to B. That is, they are the graphs that have a recursive decomposition by clique separators into smaller subgraphs. For this reason, chordal graphs have also sometimes been called decomposable graphs.[9]

Intersection graphs of subtrees

[edit]
A chordal graph with eight vertices, represented as the intersection graph of eight subtrees of a six-node tree.

An alternative characterization of chordal graphs, due to Gavril (1974), involves trees and their subtrees.

From a collection of subtrees of a tree, one can define a subtree graph, which is an intersection graph that has one vertex per subtree and an edge connecting any two subtrees that overlap in one or more nodes of the tree. Gavril showed that the subtree graphs are exactly the chordal graphs.

A representation of a chordal graph as an intersection of subtrees forms a tree decomposition of the graph, with treewidth equal to one less than the size of the largest clique in the graph; the tree decomposition of any graph G can be viewed in this way as a representation of G as a subgraph of a chordal graph. The tree decomposition of a graph is also the junction tree of the junction tree algorithm.

Relation to other graph classes

[edit]

Subclasses

[edit]

Interval graphs are the intersection graphs of subtrees of path graphs, a special case of trees. Therefore, they are a subfamily of chordal graphs.

Split graphs are graphs that are both chordal and the complements of chordal graphs. Bender, Richmond & Wormald (1985) showed that, in the limit as n goes to infinity, the fraction of n-vertex chordal graphs that are split approaches one.

Ptolemaic graphs are graphs that are both chordal and distance hereditary. Quasi-threshold graphs are a subclass of Ptolemaic graphs that are both chordal and cographs. Block graphs are another subclass of Ptolemaic graphs in which every two maximal cliques have at most one vertex in common. A special type is windmill graphs, where the common vertex is the same for every pair of cliques.

Strongly chordal graphs are graphs that are chordal and contain no n-sun (for n ≥ 3) as an induced subgraph. Here an n-sun is an n-vertex chordal graph G together with a collection of n degree-two vertices, adjacent to the edges of a Hamiltonian cycle in G.

K-trees are chordal graphs in which all maximal cliques and all maximal clique separators have the same size.[10] Apollonian networks are chordal maximal planar graphs, or equivalently planar 3-trees.[10] Maximal outerplanar graphs are a subclass of 2-trees, and therefore are also chordal.

Superclasses

[edit]

Chordal graphs are a subclass of the well known perfect graphs. Other superclasses of chordal graphs include weakly chordal graphs, cop-win graphs, odd-hole-free graphs, even-hole-free graphs, and Meyniel graphs. Chordal graphs are precisely the graphs that are both odd-hole-free and even-hole-free (see holes in graph theory).

Every chordal graph is a strangulated graph, a graph in which every peripheral cycle is a triangle, because peripheral cycles are a special case of induced cycles. Strangulated graphs are graphs that can be formed by clique-sums of chordal graphs and maximal planar graphs. Therefore, strangulated graphs include maximal planar graphs.[11]

Chordal completions and treewidth

[edit]
Main article: Chordal completion

If G is an arbitrary graph, a chordal completion of G (or minimum fill-in) is a chordal graph that contains G as a subgraph. The parameterized version of minimum fill-in is fixed parameter tractable, and moreover, is solvable in parameterized subexponential time.[12][13] The treewidth of G is one less than the number of vertices in a maximum clique of a chordal completion chosen to minimize this clique size. The k-trees are the graphs to which no additional edges can be added without increasing their treewidth to a number larger than k. Therefore, the k-trees are their own chordal completions, and form a subclass of the chordal graphs. Chordal completions can also be used to characterize several other related classes of graphs.[14]

Notes

[edit]

References

[edit]
[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Chordal graph

View on Grokipedia
from Grokipedia
A chordal graph is an undirected graph in which every cycle of length four or more has a chord, an edge connecting two non-adjacent vertices of the cycle, ensuring no induced cycles longer than three vertices exist. These graphs, also known as triangulated or rigid-circuit graphs, form an important subclass of perfect graphs, where the chromatic number equals the number for every . Chordal graphs are characterized by the existence of a perfect elimination ordering (PEO), a vertex ordering where, for each vertex, its later neighbors form a , allowing linear-time recognition and efficient algorithms for problems like maximum finding. They also admit a clique tree representation, where maximal s are nodes in a such that intersections of cliques along paths satisfy the induced subtree property, facilitating decompositions useful in . Every chordal graph has at least two simplicial vertices—those whose neighbors induce a —and minimal vertex separators are themselves s. The study of chordal graphs dates to the , with early work by Berge linking them to perfect graphs and applications, and key characterizations as intersection graphs of subtrees in a emerging in the from Dirac, Gavril, and others. Notable applications include sparse matrix factorizations like zero-fill , semidefinite optimization for exploiting sparsity, positive semidefinite matrix completion, and probabilistic graphical models such as Bayesian networks. In , chordal structures enable polynomial-time solutions for vertex coloring, , and related problems that are NP-hard in general graphs.

Definition and Characterizations

Formal Definition

A chordal graph is an undirected simple graph in which every cycle of length at least four has at least one chord, an edge that connects two non-adjacent vertices of the cycle. The concept was first studied in 1958 by Hajnal and Surányi, who characterized such graphs as those without induced cycles of length greater than or equal to four, though the term "chordal" was coined later by Gavril in 1974 to distinguish them from other uses of "triangulated graphs," with earlier names including "rigid circuit graphs" as used by Dirac in 1961. Examples of chordal graphs include complete graphs, which contain no chordless cycles of length four or more since all possible edges are present, and trees, which are acyclic and thus trivially satisfy the condition. Interval graphs, defined as intersection graphs of intervals on the real line, form a proper subclass of chordal graphs. In contrast, any CnC_n for n≥4n \geq 4 without additional edges is non-chordal, with C4C_4 being the smallest such example as it forms an induced cycle lacking a chord. Equivalently, chordal graphs are precisely the undirected graphs that contain no induced cycle of length four or more (i.e., no chordless cycles of that length).

Perfect Elimination Ordering

A perfect elimination ordering (PEO) of an undirected graph G=(V,E)G = (V, E) is a linear ordering of the vertices v1,v2,…,vnv_1, v_2, \dots, v_n such that, for each index i=1,2,…,ni = 1, 2, \dots, n, the neighbors of viv_i that appear after viv_i in the ordering (i.e., in {vi+1,…,vn}\{v_{i+1}, \dots, v_n\}) induce a in GG. This ordering captures a structural property where each vertex can be "eliminated" without introducing chords to non-adjacent neighbors later in the sequence. A fundamental characterization of chordal graphs is that a graph is chordal if and only if it admits a PEO. This equivalence is proved using a simplicial elimination scheme: starting from a chordal graph, repeatedly remove a simplicial vertex—a vertex whose entire neighborhood induces a —yields a PEO in reverse, and the process preserves chordality. Every chordal graph contains at least one simplicial vertex, and if the graph is non-complete and has at least two vertices, it contains at least two non-adjacent simplicial vertices. Thus, a PEO can be constructed by iteratively selecting and eliminating such vertices until the graph is empty, though efficient linear-time algorithms for finding a PEO are discussed in later sections on recognition. As an illustrative example, consider trees, which are chordal graphs. In a tree, leaves are simplicial vertices, and any ordering obtained by repeatedly removing leaves—such as a leaf-to-root traversal in a rooted —serves as a PEO, since the later neighbors of each vertex (its or children toward the ) always form a trivial . This highlights how the PEO property aligns with the acyclic structure of trees while generalizing to more complex chordal graphs.

Subtree Intersection Graphs

A chordal graph can be characterized as the of subtrees of a , where each vertex of the graph corresponds to a subtree, and two vertices are adjacent their corresponding subtrees have a non-empty . This equivalence was established by Gavril in 1974, who proved that a graph is chordal it is the of subtrees in some . A specific construction realizing this characterization is the clique tree of the chordal graph, also known as the intersection tree. In this representation, the nodes of the tree are the maximal cliques of the graph, and each edge connects two maximal cliques whose intersection is a minimal vertex separator of the graph. For each vertex vv in the original graph, the subtree corresponding to vv consists of all nodes (maximal cliques) in the clique tree that contain vv, forming a connected subtree due to the properties of chordal graphs. An illustrative example arises with interval graphs, a subclass of chordal graphs, where the host tree is a path and the subtrees are subpaths (intervals) on that path. For arbitrary chordal graphs, the host tree in the subtree intersection representation is a more general beyond a mere path.

Recognition and Computation

Algorithms for Recognition

A chordal graph can be recognized efficiently using ordering-based algorithms that attempt to produce a perfect elimination ordering (PEO) and verify its validity. These methods leverage the characterization that a graph is chordal it admits a PEO, allowing recognition in linear time relative to the number of vertices nn and edges mm. One such algorithm is the Maximum Cardinality Search (MCS), which iteratively selects the vertex with the largest number of already numbered neighbors as the next in the ordering, starting from an arbitrary vertex and proceeding backwards. If the resulting ordering is a PEO, the graph is chordal; otherwise, it is not. MCS can be implemented to run in O(n+m)O(n + m) time by maintaining a list of vertices sorted by their labels using appropriate data structures. An alternative is the Lexicographic (Lex-BFS), which performs a while prioritizing vertices with the lexicographically largest labels based on the order in which their neighbors were visited. Like MCS, Lex-BFS produces a PEO for chordal graphs and can be executed in O(n+m)O(n + m) time, making it suitable for recognition. To verify whether an ordering σ\sigma is a PEO, the algorithm checks for each vertex vv (in the reverse order of σ\sigma) that the neighbors of vv that appear later in σ\sigma form a . This is done by ensuring that the first such neighbor is adjacent to all others, which can be confirmed by examining adjacency lists in O(n+m)O(n + m) total time across all vertices. Both MCS and Lex-BFS were introduced as linear-time recognition algorithms for chordal graphs by , Tarjan, and Lueker. Their correctness relies on the property that, for a chordal graph, these searches yield a PEO; if the verification fails, the graph contains a chordless cycle of length at least four, as the failure point identifies non-adjacent neighbors that, together with earlier vertices, form such a cycle.

Computing Elimination Orderings and Cliques

Assuming the graph is chordal, a perfect elimination ordering (PEO) can be computed efficiently using the maximum cardinality search (MCS) algorithm, which runs in O(n+m)O(n + m) time. The MCS proceeds as follows: initialize all vertices with label 0; for ii from nn down to 1, select an unnumbered vertex vv with the maximum label, assign it the number ii, and increment the labels of all its unnumbered neighbors by 1. The resulting ordering σ\sigma, where vertices are numbered from 1 to nn, has the property that the reverse ordering (eliminating low-numbered vertices first) is a PEO. In chordal graphs, MCS always produces a valid PEO, and the algorithm's simplicity enables implementation with appropriate data structures, such as buckets for labels. Given a PEO α=v1,…,vn\alpha = v_1, \dots, v_n (where v1v_1 is eliminated first), the cliques formed during elimination are the sets Ci={vi}∪N+(vi)C_i = \{v_i\} \cup N^+(v_i), where N+(vi)N^+(v_i) is the set of neighbors of viv_i that appear after viv_i in α\alpha. Each CiC_i induces a , and the maximal cliques are precisely those CiC_i that are not properly contained in any other CjC_j. Since there are at most nn such sets and their total description size is O(n+m)O(n + m), the maximal cliques can be identified in linear time by checking containments. These maximal cliques can subsequently be connected via their intersections to form a representation of the graph. The enumeration runs in O(n+m)O(n + m) time by scanning the adjacency lists along the PEO. For example, consider a chordal graph with vertices {a,b,c,d}\{a, b, c, d\} and edges {a\{a-bb, aa-cc, bb-cc, bb-d}d\}. Applying MCS (starting arbitrarily with bb numbered 4, labels of a,c,da, c, d to 1; then aa numbered 3, label of cc to 2; then cc numbered 2; then dd numbered 1), the PEO is d,c,a,bd, c, a, b (positions 1 to 4). The sets are: Cd={d,b}C_d = \{d, b\}; Cc={c,a,b}C_c = \{c, a, b\} (since N+(c)={a,b}N^+(c) = \{a, b\}); Ca={a,b}C_a = \{a, b\}; Cb=∅C_b = \emptyset. Among these, {d,b}\{d, b\} and {c,a,b}\{c, a, b\} are maximal, as {a,b}\{a, b\} is contained in {c,a,b}\{c, a, b\}.

Structural Properties

Maximal Cliques and Separators

In chordal graphs, the maximal cliques form the fundamental building blocks of the graph's structure and can be enumerated efficiently. Specifically, given a perfect elimination ordering, an can list all maximal cliques in linear time relative to the size of the graph, by identifying the neighborhoods of vertices during the elimination process. This efficiency stems from the fact that each maximal clique corresponds to a simplicial vertex's neighborhood at the time of its elimination, allowing the cliques to be output without . A minimal separator in a graph is defined as an inclusion-minimal vertex set whose removal disconnects two non-adjacent vertices, thereby separating them into different connected components. In chordal graphs, every such minimal separator induces a complete subgraph, or . Moreover, these minimal separators are exactly the cliques that separate distinct components of the graph after removal, ensuring that no smaller subset achieves the same disconnection. This property distinguishes chordal graphs, as non-chordal graphs may have minimal separators that are not cliques. In a connected chordal graph, the number of edges in any clique tree equals the number of maximal cliques minus one, and each such edge is labeled by a minimal separator given by the intersection of the two adjacent maximal cliques (with possible repetitions of the same separator on multiple edges). Thus, the number of distinct minimal separators is at most the number of maximal cliques minus one. This arises from the tree-like organization in the clique tree representation, where maximal cliques are nodes and minimal separators label the edges connecting adjacent nodes. Chordal graphs exhibit the running among their maximal s, meaning there exists a linear ordering of the cliques such that, for each clique beyond the first, its with the union of all preceding cliques is contained entirely within the immediately previous clique. This facilitates the construction of clique trees and underscores the -based characterizations of chordal graphs. For instance, in the clique tree of a chordal graph—where nodes represent maximal cliques and edges connect cliques whose is nonempty—the minimal separator associated with each tree edge is precisely the of the two adjacent maximal cliques. This serves as the separator between the subtrees rooted at those nodes, illustrating how separators bridge the clique structure.

Coloring and Perfectness

Chordal graphs possess a perfect elimination ordering (PEO), which enables an efficient for . Given a PEO σ=v1,v2,…,vn\sigma = v_1, v_2, \dots, v_n of the graph GG, where v1v_1 is simplicial and for each i>1i > 1, the neighbors of viv_i in {v1,…,vi−1}\{v_1, \dots, v_{i-1}\} induce a , the coloring proceeds in the reverse order vn,vn−1,…,v1v_n, v_{n-1}, \dots, v_1. For each vertex viv_i, assign the smallest color not used by its already colored neighbors (those in {vi+1,…,vn}\{v_{i+1}, \dots, v_n\}). The PEO property ensures that these neighbors induce a in the subgraph remaining at that step, so at most ω(G)\omega(G) colors are needed, where ω(G)\omega(G) is the size of the largest in GG. This approach yields an optimal coloring, as the number of colors used equals ω(G)\omega(G). A proof proceeds by induction on the number of vertices: for the base case of a single vertex, χ(G)=ω(G)=1\chi(G) = \omega(G) = 1; assuming the result holds for n−1n-1 vertices, remove a simplicial vertex vnv_n whose neighbors form a of size at most ω(G)−1\omega(G) - 1, color the remaining graph optimally with ω(G∖vn)\omega(G \setminus v_n) colors, and extend the coloring to vnv_n using an available color without exceeding ω(G)\omega(G). By induction, χ(G∖vn)=ω(G∖vn)≤ω(G)\chi(G \setminus v_n) = \omega(G \setminus v_n) \leq \omega(G). The neighbors of vnv_n form a of size at most ω(G)−1\omega(G) - 1, so they use at most ω(G)−1\omega(G) - 1 colors, leaving at least one color available among the ω(G)\omega(G) colors for vnv_n. Chordal graphs are perfect, meaning that for every induced subgraph HH, the chromatic number χ(H)\chi(H) equals the clique number ω(H)\omega(H). This follows from the PEO characterization, which restricts to a PEO of any induced subgraph, ensuring optimal coloring as above. Additionally, chordal graphs contain no induced cycles of length at least four, hence no odd holes (induced odd cycles of length at least five) or their complements (odd antiholes), so perfection holds by the strong perfect graph theorem. The coloring algorithm runs in O(n+m)O(n + m) time, where nn is the number of vertices and mm the number of edges, as a PEO can be computed in linear time using , and the is a single pass over the vertices and their adjacency lists. This polynomial-time solvability extends to other NP-hard problems on general graphs, such as and , which reduce to coloring on chordal graphs.

Relations to Other Graph Classes

Subclasses

Interval graphs form an important subclass of chordal graphs, defined as the intersection graphs of closed intervals on the real line, where each vertex corresponds to an interval and edges connect intervals that intersect. This representation ensures that interval graphs are chordal, as any induced cycle of length four or more would contradict the linear ordering of intervals without chords. Additionally, interval graphs are characterized by the consecutive ones property: there exists a row of the vertex-clique such that the 1's in each row appear consecutively. This property enables linear-time recognition algorithms and underscores their additional structural simplicity compared to general chordal graphs. Split graphs constitute another fundamental subclass of chordal graphs, where the vertex set can be partitioned into a KK and an independent set II, with edges between KK and II being arbitrary. All split graphs are chordal because they are (2K2,C4,C5)(2K_2, C_4, C_5)-free, avoiding the induced cycles that characterize non-chordal graphs. This partition provides a structure, facilitating efficient algorithms for optimization problems like coloring, where the chromatic number equals the clique number. Threshold graphs are a proper subclass of split graphs (and thus chordal), obtainable by starting from the empty graph and repeatedly adding either an isolated vertex or a dominating vertex (adjacent to all existing vertices). They are characterized by degree sequences satisfying specific conditions or as (2K2,P4,C4)(2K_2, P_4, C_4)-free graphs. This construction yields even more restricted structure, with threshold graphs exhibiting unique properties like being both split and cographs, enabling constant-time recognition via degree sequences. Chordal bipartite graphs represent the bipartite subclass of chordal graphs, consisting of bipartite graphs with no induced cycle of length six or longer. As a -like subclass in the sense that their structure often decomposes into representations of bipartite s, they inherit chordality while maintaining bipartiteness, and admit efficient algorithms for matching and flow problems due to their acyclic chordal nature in even cycles. These subclasses collectively exhibit enhanced computational tractability over general chordal graphs, such as polynomial-time solutions for problems like maximum via their or partition models.

Superclasses

Chordal graphs form a subclass of perfect graphs, where a graph is perfect if, for every , the chromatic number equals the clique number. This inclusion follows from the property that chordal graphs admit a perfect elimination ordering, which enables to achieve the optimal chromatic number equal to the size of the maximum . The perfection of chordal graphs was established early in the study of perfect graphs, predating the strong perfect graph theorem. Weakly chordal graphs provide another superclass of chordal graphs, defined as graphs in which neither the graph nor its complement contains an induced cycle of length at least five (known as holes or antiholes). Chordal graphs satisfy this condition since they contain no induced cycles of length four or more, making them a proper subclass. Weakly chordal graphs generalize chordal graphs by allowing certain induced cycles of length four while still ensuring perfectness and efficient algorithmic solvability for optimization problems like coloring. Meyniel graphs constitute yet another superclass, characterized by the condition that every odd cycle of length at least five has at least two chords. Chordal graphs vacuously satisfy this, as they have no such cycles, and Meyniel graphs are known to be perfect. This class relaxes the chordal condition by permitting some odd holes with multiple chords. The classes of chordal graphs and s are incomparable: not every planar graph is chordal, as the C5C_5 is planar but induces a chordless cycle of length five, and not every chordal graph is planar, as the K5K_5 is chordal but non-planar by Kuratowski's theorem.

Completions and Width Parameters

Chordal Completions

A chordal completion of an undirected graph GG is a chordal supergraph on the same vertex set that includes all edges of GG, obtained by adding a set of edges to eliminate induced cycles of length four or more. A minimal chordal completion is one where removing any added edge results in a non-chordal graph, ensuring no superfluous edges are introduced. The minimum fill-in problem seeks a chordal completion with the smallest number of added edges, which is NP-complete. This complexity arises from the challenge of optimally triangulating the graph while minimizing structural increases. Approximations for the minimum fill-in can leverage related graph parameters, though exact solutions remain intractable for general graphs. To compute a minimal chordal completion, the MCS-M employs maximum search (MCS), an ordering that simulates elimination and identifies necessary fill-in edges. During the process, MCS labels vertices by selecting those adjacent to the most previously labeled vertices, revealing a perfect elimination ordering (PEO) in chordal graphs or adding edges to enforce one in non-chordal cases. This approach runs in linear time relative to the graph size and produces a minimal set of fill-ins by verifying irredundancy at each step. Every graph admits a chordal completion, as adding edges to form a yields a trivial chordal supergraph. More refined completions relate to graphs embeddable as partial kk-trees for some kk, where the added edges bound the resulting structure. Chordal completions find key applications in , particularly of symmetric positive definite matrices, where fill-in edges correspond to nonzeros introduced during elimination. By computing a chordal completion via an appropriate ordering, such as one from MCS, the avoids excessive density while preserving sparsity patterns, enabling efficient numerical solutions in large-scale computations.

Treewidth Connection

Treewidth is a graph parameter that measures the "tree-likeness" of a graph, defined as the minimum width over all possible tree decompositions of the graph, where the width of a decomposition is the size of the largest bag minus one. For chordal graphs, this parameter has a particularly simple characterization: the treewidth equals the size of the largest clique minus one, denoted \tw(G)=ω(G)−1\tw(G) = \omega(G) - 1. This equality holds because in a chordal graph, a clique tree provides an optimal tree decomposition where each bag is a maximal clique, ensuring that the maximum bag size is precisely ω(G)\omega(G). A fundamental structural theorem links chordality directly to tree decompositions: a graph is chordal if and only if it admits a tree decomposition in which every bag induces a clique, known as a clique tree. In such a decomposition, the nodes of the tree correspond to the maximal cliques of the graph, and the intersection properties ensure that the decomposition satisfies the running intersection property required for tree decompositions. This characterization not only confirms the treewidth formula but also provides a combinatorial representation of chordal graphs that facilitates algorithmic exploitation of their structure. Computing the treewidth of a chordal graph is thus equivalent to finding the size of its maximum , which can be done efficiently using algorithms based on perfect elimination orderings. For general graphs, treewidth computation is NP-hard, but chordal graphs serve as approximations: the treewidth of any graph is the minimum over all chordal supergraphs HH of ω(H)−1\omega(H) - 1. This connection underscores the role of chordal graphs in bounding for broader classes. The treewidth connection enables powerful algorithmic techniques for chordal graphs, particularly dynamic programming over the clique tree to solve optimization problems such as maximum independent set or in time polynomial in the graph size and exponential only in the treewidth (which is ω(G)−1\omega(G) - 1). This approach leverages the bounded size of cliques in the bags, making chordal graphs amenable to exact solutions for NP-hard problems when the clique number is small.

References

  1. https://www.seas.ucla.edu/~vandenbe/publications/chordalsdp.pdf
  2. https://www.sciencedirect.com/science/article/pii/009589567490094X
  3. https://epubs.siam.org/doi/10.1137/1.9780898719802.ch2
  4. https://link.springer.com/article/10.1007/BF02992776
  5. https://eudml.org/doc/213681
  6. http://cse.unl.edu/~choueiry/Documents/TriangulationDJRose1970.pdf
  7. http://people.math.binghamton.edu/zaslav/Oldcourses/580.S13/blair-peyton.chordal-graphs-clique-trees.ornl1992.pdf
  8. https://www.sciencedirect.com/science/article/pii/S0166218X09000390
  9. https://www.math.u-szeged.hu/~hajnal/courses/PhD_Specialis/Gavril.pdf
  10. https://epubs.siam.org/doi/10.1137/0213035
  11. https://epubs.siam.org/doi/10.1137/0205021
  12. https://digital.library.unt.edu/ark:/67531/metadc1319152/m2/1/high_res_d/10145949.pdf
  13. https://doi.org/10.1007/BF02992776
  14. http://matwbn.icm.edu.pl/ksiazki/fm/fm51/fm5115.pdf
  15. https://mathworld.wolfram.com/SplitGraph.html
  16. https://www.sciencedirect.com/science/article/pii/S0304397516000517
  17. https://hal.science/hal-00001574v1/document
  18. https://www.dam.brown.edu/people/mumford/vision/papers/1994d--ChordalCompl-NC.pdf
  19. https://link.springer.com/chapter/10.1007/3-540-36379-3_1
  20. https://epubs.siam.org/doi/10.1137/0602010
  21. https://www.cs.purdue.edu/homes/apothen/Papers/elimination-DS2004.pdf
  22. https://www.labri.fr/perso/mazoit/pdfs/Treewidth_of_planar_graphs_conf.pdf
  23. http://people.tamu.edu/~chliu/teaching/spring24math662/2024_03_27.pdf
  24. https://ajc.maths.uq.edu.au/pdf/80/ajc_v80_p089.pdf
  25. https://www.labri.fr/perso/mbonamy/917U/7-Treewidth.pdf
  26. https://ics-archive.science.uu.nl/research/techreps/repo/CS-2001/2001-49.pdf
  27. http://bitsavers.informatik.uni-stuttgart.de/pdf/mit/lcs/tr/MIT-LCS-TR-0394.pdf
Add your contribution
Related Hubs
User Avatar
No comments yet.