Chordal completion
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.
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.
Related graph families
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]
References
- ^ a b 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.
- ^ 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.
- ^ Eppstein, David (November 15, 2012), Graph parameters and cliques in supergraphs.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences (1st ed.). New York: W. H. Freeman and Company. ISBN 9780716710455. MR 0519066. OCLC 247570676., [OPEN4], p. 286; update, p. 339.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ 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.