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.Cite error: Closing </ref> missing for <ref> tag 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.[2]
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.[3]
Computational complexity
Although listed as an open problem in the 1979 book Computers and Intractability,[4] 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.[5] 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.[6] 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.[7]
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.[8]
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).[9]
References
- ↑ 1.0 1.1 Parra, Andreas; Scheffler, Petra (1997), "Characterizations and algorithmic applications of chordal graph embeddings", Discrete Applied Mathematics 79 (1–3): 171–188, doi:10.1016/S0166-218X(97)00041-3.
- ↑ "Chordal completions of planar graphs", Journal of Combinatorial Theory, Series B 62 (1): 96–106, 1994, doi:10.1006/jctb.1994.1056.
- ↑ "A characterisation of rigid circuit graphs", Discrete Mathematics 9 (3): 205–212, 1974, doi:10.1016/0012-365X(74)90002-8.
- ↑ 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.
- ↑ "Computing the minimum fill-in is NP-complete", SIAM Journal on Algebraic and Discrete Methods 2 (1): 77–79, 1981, doi:10.1137/0602010.
- ↑ 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.
- ↑ Fomin, Fedor V.; Villanger, Yngve (2013), "Subexponential parameterized algorithm for minimum fill-in", SIAM Journal on Computing 42 (6): 2197–2216, doi:10.1137/11085390X.
- ↑ "Approximating treewidth, pathwidth, frontsize, and shortest elimination tree", Journal of Algorithms 18 (2): 238–255, 1995, doi:10.1006/jagm.1995.1009.
- ↑ 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, 3142, Springer-Verlag, pp. 568–580, doi:10.1007/978-3-540-27836-8_49.
 |  |
