Chordal completion

Last updated

In graph theory, a branch of mathematics, a chordal completion of a given undirected graph G is a chordal graph, on the same vertex set, that has G as a subgraph. A minimal chordal completion is a chordal completion such that any graph formed by removing an edge would no longer be a chordal completion. A minimum chordal completion is a chordal completion with as few edges as possible.

Contents

A different type of chordal completion, one that minimizes the size of the maximum clique in the resulting chordal graph, can be used to define the treewidth of G. Chordal completions can also be used to characterize several other graph classes including AT-free graphs, claw-free AT-free graphs, and cographs.

The minimum chordal completion was one of twelve computational problems whose complexity was listed as open in the 1979 book Computers and Intractability . Applications of chordal completion include modeling the problem of minimizing fill-in when performing Gaussian elimination on sparse symmetric matrices, and reconstructing phylogenetic trees.

Chordal completions of a graph are sometimes called triangulations, [1] but this term is ambiguous even in the context of graph theory, as it can also refer to maximal planar graphs.

A graph G is an AT-free graph if and only if all of its minimal chordal completions are interval graphs. G is a claw-free AT-free graph if and only if all of its minimal chordal completions are proper interval graphs. And G is a cograph if and only if all of its minimal chordal completions are trivially perfect graphs. [1]

A graph G has treewidth at most k if and only if G has at least one chordal completion whose maximum clique size is at most k + 1. It has pathwidth at most k if and only if G has at least one chordal completion that is an interval graph with maximum clique size at most k + 1. It has bandwidth at most k if and only if G has at least one chordal completion that is a proper interval graph with maximum clique size at most k + 1. [2] And it has tree-depth k if and only if it has at least one chordal completion that is a trivially perfect graph with maximum clique size at most k. [3]

Applications

The original application of chordal completion described in Computers and Intractability involves Gaussian elimination for sparse matrices. During the process of Gaussian elimination, one wishes to minimize fill-in, coefficients of the matrix that were initially zero but later become nonzero, because the need to calculate the values of these coefficients slows down the algorithm. The pattern of nonzeros in a sparse symmetric matrix can be described by an undirected graph (having the matrix as its adjacency matrix); the pattern of nonzeros in the filled-in matrix is always a chordal graph, any minimal chordal completion corresponds to a fill-in pattern in this way. If a chordal completion of a graph is given, a sequence of steps in which to perform Gaussian elimination to achieve this fill-in pattern can be found by computing an elimination ordering of the resulting chordal graph. In this way, the minimum fill-in problem can be seen as equivalent to the minimum chordal completion problem. [4] In this application, planar graphs may arise in the solution of two-dimensional finite element systems; it follows from the planar separator theorem that every planar graph with n vertices has a chordal completion with at most O(n log n) edges. [5]

Another application comes from phylogeny, the problem of reconstructing evolutionary trees, for instance trees of organisms subject to genetic mutations or trees of sets of ancient manuscripts copied one from another subject to scribal errors. If one assumes that each genetic mutation or scribal error happens only once, one obtains a perfect phylogeny, a tree in which the species or manuscripts having any particular characteristic always form a connected subtree. As Buneman (1974) describes, the existence of a perfect phylogeny can be modeled as a chordal completion problem. One draws an "overlap graph" G in which the vertices are attribute values (specific choices for some characteristic of a species or manuscript) and the edges represent pairs of attribute values that are shared by at least one species. The vertices of the graph can be colored by the identities of the characteristics that each attribute value comes from, so that the total number of colors equals the number of characteristics used to derive the phylogeny. Then a perfect phylogeny exists if and only if G has a chordal completion that respects the coloring. [6]

Computational complexity

Although listed as an open problem in the 1979 book Computers and Intractability , [7] the computational complexity of the minimum chordal completion problem (also called the minimum fill-in problem) was quickly resolved: Yannakakis (1981) showed it to be NP-complete. [8] If the minimum chordal completion adds k edges to a graph G, then it is possible to find a chordal completion using at most 8k2 added edges, in polynomial time. [9] The problem of finding the optimal set of k edges to add can also be solved by a fixed-parameter tractable algorithm, in time polynomial in the graph size and subexponential in k. [10]

The treewidth (minimum clique size of a chordal completion) and related parameters including pathwidth and tree-depth are also NP-complete to compute, and (unless P=NP) cannot be approximated in polynomial time to within a constant factor of their optimum values; however, approximation algorithms with logarithmic approximation ratios are known for them. [11]

Both the minimum fill-in and treewidth problems can be solved in exponential time. More precisely, for an n-vertex graph, the time is O(1.9601n). [12]

Related Research Articles

<span class="mw-page-title-main">Tree decomposition</span> Mapping of a graph into a tree

In graph theory, a tree decomposition is a mapping of a graph into a tree that can be used to define the treewidth of the graph and speed up solving certain computational problems on the graph.

<span class="mw-page-title-main">Clique problem</span> Task of computing complete subgraphs

In computer science, the clique problem is the computational problem of finding cliques in a graph. It has several different formulations depending on which cliques, and what information about the cliques, should be found. Common formulations of the clique problem include finding a maximum clique, finding a maximum weight clique in a weighted graph, listing all maximal cliques, and solving the decision problem of testing whether a graph contains a clique larger than a given size.

<span class="mw-page-title-main">Interval graph</span> Intersection graph for intervals on the real number line

In graph theory, an interval graph is an undirected graph formed from a set of intervals on the real line, with a vertex for each interval and an edge between vertices whose intervals intersect. It is the intersection graph of the intervals.

<span class="mw-page-title-main">Independent set (graph theory)</span> Unrelated vertices in graphs

In graph theory, an independent set, stable set, coclique or anticlique is a set of vertices in a graph, no two of which are adjacent. That is, it is a set of vertices such that for every two vertices in , there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in . A set is independent if and only if it is a clique in the graph's complement. The size of an independent set is the number of vertices it contains. Independent sets have also been called "internally stable sets", of which "stable set" is a shortening.

<span class="mw-page-title-main">Chordal graph</span> Graph where all long cycles have a chord

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 or triangulated graphs.

<span class="mw-page-title-main">Circle graph</span> Intersection graph of a chord diagram

In graph theory, a circle graph is the intersection graph of a chord diagram. That is, it is an undirected graph whose vertices can be associated with a finite system of chords of a circle such that two vertices are adjacent if and only if the corresponding chords cross each other.

In graph theory, the treewidth of an undirected graph is an integer number which specifies, informally, how far the graph is from being a tree. The smallest treewidth is 1; the graphs with treewidth 1 are exactly the trees and the forests. The graphs with treewidth at most 2 are the series–parallel graphs. The maximal graphs with treewidth exactly k are called k-trees, and the graphs with treewidth at most k are called partial k-trees. Many other well-studied graph families also have bounded treewidth.

In graph theory, a path decomposition of a graph G is, informally, a representation of G as a "thickened" path graph, and the pathwidth of G is a number that measures how much the path was thickened to form G. More formally, a path-decomposition is a sequence of subsets of vertices of G such that the endpoints of each edge appear in one of the subsets and such that each vertex appears in a contiguous subsequence of the subsets, and the pathwidth is one less than the size of the largest set in such a decomposition. Pathwidth is also known as interval thickness, vertex separation number, or node searching number.

<span class="mw-page-title-main">Clique-width</span> Measure of graph complexity

In graph theory, the clique-width of a graph G is a parameter that describes the structural complexity of the graph; it is closely related to treewidth, but unlike treewidth it can be small for dense graphs. It is defined as the minimum number of labels needed to construct G by means of the following 4 operations :

  1. Creation of a new vertex v with label i (denoted by i(v))
  2. Disjoint union of two labeled graphs G and H (denoted by )
  3. Joining by an edge every vertex labeled i to every vertex labeled j (denoted by η(i,j)), where i ≠ j
  4. Renaming label i to label j (denoted by ρ(i,j))

In graph theory, a clique cover or partition into cliques of a given undirected graph is a partition of the vertices into cliques, subsets of vertices within which every two vertices are adjacent. A minimum clique cover is a clique cover that uses as few cliques as possible. The minimum k for which a clique cover exists is called the clique cover number of the given graph.

<span class="mw-page-title-main">Clique-sum</span> Gluing graphs at complete subgraphs

In graph theory, a branch of mathematics, a clique-sum is a way of combining two graphs by gluing them together at a clique, analogous to the connected sum operation in topology. If two graphs G and H each contain cliques of equal size, the clique-sum of G and H is formed from their disjoint union by identifying pairs of vertices in these two cliques to form a single shared clique, and then possibly deleting some of the clique edges. A k-clique-sum is a clique-sum in which both cliques have at most k vertices. One may also form clique-sums and k-clique-sums of more than two graphs, by repeated application of the two-graph clique-sum operation.

In graph theory and theoretical computer science, the longest path problem is the problem of finding a simple path of maximum length in a given graph. A path is called simple if it does not have any repeated vertices; the length of a path may either be measured by its number of edges, or by the sum of the weights of its edges. In contrast to the shortest path problem, which can be solved in polynomial time in graphs without negative-weight cycles, the longest path problem is NP-hard and the decision version of the problem, which asks whether a path exists of at least some given length, is NP-complete. This means that the decision problem cannot be solved in polynomial time for arbitrary graphs unless P = NP. Stronger hardness results are also known showing that it is difficult to approximate. However, it has a linear time solution for directed acyclic graphs, which has important applications in finding the critical path in scheduling problems.

In graph theory, the tree-depth of a connected undirected graph is a numerical invariant of , the minimum height of a Trémaux tree for a supergraph of . This invariant and its close relatives have gone under many different names in the literature, including vertex ranking number, ordered chromatic number, and minimum elimination tree height; it is also closely related to the cycle rank of directed graphs and the star height of regular languages. Intuitively, where the treewidth of a graph measures how far it is from being a tree, this parameter measures how far a graph is from being a star.

<span class="mw-page-title-main">Caterpillar tree</span> Tree graph with all nodes within distance 1 from central path

In graph theory, a caterpillar or caterpillar tree is a tree in which all the vertices are within distance 1 of a central path.

In graph theory, the graph bandwidth problem is to label the n vertices vi of a graph G with distinct integers so that the quantity is minimized . The problem may be visualized as placing the vertices of a graph at distinct integer points along the x-axis so that the length of the longest edge is minimized. Such placement is called linear graph arrangement, linear graph layout or linear graph placement.

In the mathematical field of graph theory, the intersection number of a graph is the smallest number of elements in a representation of as an intersection graph of finite sets. In such a representation, each vertex is represented as a set, and two vertices are connected by an edge whenever their sets have a common element. Equivalently, the intersection number is the smallest number of cliques needed to cover all of the edges of .

<span class="mw-page-title-main">Dense subgraph</span> Highly connected subgraph

In graph theory and computer science, a dense subgraph is a subgraph with many edges per vertex. This is formalized as follows: let G = (V, E) be an undirected graph and let S = (VS, ES) be a subgraph of G. Then the density of S is defined to be:

In graph theory, a branch of mathematics, an indifference graph is an undirected graph constructed by assigning a real number to each vertex and connecting two vertices by an edge when their numbers are within one unit of each other. Indifference graphs are also the intersection graphs of sets of unit intervals, or of properly nested intervals. Based on these two types of interval representations, these graphs are also called unit interval graphs or proper interval graphs; they form a subclass of the interval graphs.

<span class="mw-page-title-main">Cutwidth</span> Property in graph theory

In graph theory, the cutwidth of an undirected graph is the smallest integer with the following property: there is an ordering of the vertices of the graph, such that every cut obtained by partitioning the vertices into earlier and later subsets of the ordering is crossed by at most edges. That is, if the vertices are numbered , then for every , the number of edges with and is at most .

References

  1. 1 2 Parra, Andreas; Scheffler, Petra (1997), "Characterizations and algorithmic applications of chordal graph embeddings", 4th Twente Workshop on Graphs and Combinatorial Optimization (Enschede, 1995), Discrete Applied Mathematics , 79 (1–3): 171–188, doi:10.1016/S0166-218X(97)00041-3, MR   1478250 .
  2. ↑ Kaplan, Haim; Shamir, Ron (1996), "Pathwidth, bandwidth, and completion problems to proper interval graphs with small cliques", SIAM Journal on Computing , 25 (3): 540–561, doi:10.1137/S0097539793258143, MR   1390027 .
  3. ↑ Eppstein, David (November 15, 2012), Graph parameters and cliques in supergraphs .
  4. ↑ Rose, Donald J. (1972), "A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations", Graph theory and computing, Academic Press, New York, pp. 183–217, MR   0341833 .
  5. ↑ Chung, F. R. K.; Mumford, David (1994), "Chordal completions of planar graphs", Journal of Combinatorial Theory , Series B, 62 (1): 96–106, doi: 10.1006/jctb.1994.1056 , MR   1290632 .
  6. ↑ Buneman, Peter (1974), "A characterisation of rigid circuit graphs", Discrete Mathematics , 9 (3): 205–212, doi: 10.1016/0012-365X(74)90002-8 , MR   0357218 .
  7. ↑ Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness , W. H. Freeman, ISBN   0-7167-1045-5 , [OPEN4], p. 286; update, p. 339.
  8. ↑ Yannakakis, Mihalis (1981), "Computing the minimum fill-in is NP-complete", SIAM Journal on Algebraic and Discrete Methods, 2 (1): 77–79, CiteSeerX   10.1.1.128.192 , doi:10.1137/0602010, hdl:10338.dmlcz/140775, MR   0604513 .
  9. ↑ Natanzon, Assaf; Shamir, Ron; Sharan, Roded (2000), "A polynomial approximation algorithm for the minimum fill-in problem", SIAM Journal on Computing , 30 (4): 1067–1079, doi:10.1137/S0097539798336073, MR   1786752 .
  10. ↑ Fomin, Fedor V.; Villanger, Yngve (2013), "Subexponential parameterized algorithm for minimum fill-in", SIAM Journal on Computing , 42 (6): 2197–2216, arXiv: 1104.2230 , doi:10.1137/11085390X, MR   3138120 .
  11. ↑ Bodlaender, Hans L.; Gilbert, John R.; Hafsteinsson, Hjálmtýr; Kloks, Ton (1995), "Approximating treewidth, pathwidth, frontsize, and shortest elimination tree", Journal of Algorithms, 18 (2): 238–255, doi:10.1006/jagm.1995.1009, MR   1317666 .
  12. ↑ Fomin, Fedor V.; Kratsch, Dieter; Todinca, Ioan (2004), "Exact (exponential) algorithms for treewidth and minimum fill-In", Automata, Languages and Programming: 31st International Colloquium, ICALP 2004, Turku, Finland, July 12-16, 2004, Proceedings, Lecture Notes in Computer Science, vol. 3142, Springer-Verlag, pp. 568–580, doi:10.1007/978-3-540-27836-8_49 .
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.