×

Strongly chordal and chordal bipartite graphs are sandwich monotone. (English) Zbl 1230.90161

Summary: A graph class is sandwich monotone if, for every pair of its graphs \(G _{1}=(V,E _{1})\) and \(G _{2}=(V,E _{2})\) with \(E _{1}\subset E _{2}\), there is an ordering \(e _{1},\dots ,e _{k }\) of the edges in \(E _{2}\setminus E _{1}\) such that \(G=(V,E _{1}\cup \{e _{1},\dots ,e _{i }\})\) belongs to the class for every \(i\) between 1 and \(k\). In this paper we show that strongly chordal graphs and chordal bipartite graphs are sandwich monotone, answering an open question by M. Bakonyi and A. Bono [Czech. Math. J. 47, No. 4, 577–583 (1997; Zbl 0898.05043)]. So far, very few classes have been proved to be sandwich monotone, and the most famous of these are chordal graphs. Sandwich monotonicity of a graph class implies that minimal completions of arbitrary graphs into that class can be recognized and computed in polynomial time. For minimal completions into strongly chordal or chordal bipartite graphs no polynomial-time algorithm has been known. With our results such algorithms follow for both classes. In addition, from our results it follows that all strongly chordal graphs and all chordal bipartite graphs with edge constraints can be listed efficiently.

MSC:

90C27 Combinatorial optimization
05C75 Structural characterization of families of graphs

Citations:

Zbl 0898.05043
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alon N, Shapira A (2005) Every monotone graph property is testable. In: STOC 2005, pp 128–137 · Zbl 1192.68466
[2] Bakonyi M, Bono A (1997) Several results on chordal bipartite graphs. Czechoslov Math J 46:577–583 · Zbl 0898.05043 · doi:10.1023/A:1022806215452
[3] Balogh J, Bolobás B, Weinreich D (2002) Measures on monotone properties of graphs. Discrete Appl Math 116:17–36 · Zbl 0994.05077 · doi:10.1016/S0166-218X(01)00175-5
[4] Bodlaender HL, Koster AMCA (2006) Safe separators for treewidth. Discrete Math 306:337–350 · Zbl 1084.05065 · doi:10.1016/j.disc.2005.12.017
[5] Bouchitté V, Todinca I (2001) Treewidth and minimum fill-in: grouping the minimal separators. SIAM J Comput 31:212–232 · Zbl 0987.05085 · doi:10.1137/S0097539799359683
[6] Burzyn P, Bonomo F, Duran G (2000) NP-completeness results for edge modification problems. Discrete Appl Math 99:367–400 · Zbl 0940.05064 · doi:10.1016/S0166-218X(99)00146-8
[7] Dahlhaus E (1991) Chordale graphen im besonderen hinblick auf parallele algorithmen. Habilitation Thesis, Universitöt Bonn
[8] de Figueiredo CMH, Faria L, Klein S, Sritharan R (2007) On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs. Theor Comput Sci 381:57–67 · Zbl 1188.68211 · doi:10.1016/j.tcs.2007.04.007
[9] Farber M (1983) Characterizations on strongly chordal graphs. Discrete Math 43:173–189 · Zbl 0514.05048 · doi:10.1016/0012-365X(83)90154-1
[10] Fomin FV, Kratsch D, Todinca I, Villanger Y (2008) Exact algorithms for treewidth and minimum fill-in. SIAM J Comput 38:1058–1079 · Zbl 1163.05320 · doi:10.1137/050643350
[11] Goldberg PW, Golumbic MC, Kaplan H, Shamir R (1995) Four strikes against physical mapping of DNA. J Comput Bio 2:139–152 · doi:10.1089/cmb.1995.2.139
[12] Golumbic MC (2004) Algorithmic graph theory and perfect graphs, 2nd edn. Annals of Discrete Mathematics, vol 57. Elsevier, Amsterdam · Zbl 1050.05002
[13] Heggernes P, Mancini F (2009) Minimal split completions. Discrete Appl Math 157:2659–2669 · Zbl 1211.05136 · doi:10.1016/j.dam.2008.08.010
[14] Heggernes P, Papadopoulos C (2009) Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions. Theor Comput Sci 410:1–15 · Zbl 1161.68040 · doi:10.1016/j.tcs.2008.07.020
[15] Heggernes P, Suchan K, Todinca I, Villanger Y (2007) Characterizing minimal interval completions: towards better understanding of profile and pathwidth. In: STACS 2007. LNCS, vol 4393. Springer, Berlin, pp 236–247 · Zbl 1171.68620
[16] Kaplan H, Shamir R, Tarjan RE (1999) Tractability of parameterized completion problems on chordal, strongly chordal, and proper interval graphs. SIAM J Comput 28:1906–1922 · Zbl 0928.68124 · doi:10.1137/S0097539796303044
[17] Kijima S, Kiyomi M, Okamoto Y, Uno T (2008) On listing, sampling, and counting the chordal graphs with edge constraints. In: COCOON 2008. LNCS, vol 5092. Springer, Berlin, pp 458–467 · Zbl 1148.68419
[18] Lokshtanov D, Mancini F, Papadopoulos C (2008) Characterizing and computing minimal cograph completions. In: FAW 2008. LNCS, vol 5059. Springer, Berlin, pp 147–158 · Zbl 1143.68506
[19] Natanzon A, Shamir R, Sharan R (2001) Complexity classification of some edge modification problems. Discrete Appl Math 113:109–128 · Zbl 0982.68104 · doi:10.1016/S0166-218X(00)00391-7
[20] Paige R, Tarjan RE (1987) Three partition refinement algorithms. SIAM J Comput 16:973–989 · Zbl 0654.68072 · doi:10.1137/0216062
[21] Rose D (1970) Triangulated graphs and the elimination process. J Math Anal Appl 32:597–609 · Zbl 0216.02602 · doi:10.1016/0022-247X(70)90282-9
[22] Rose DJ (1972) A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations. In: Read RC (ed) Graph theory and computing. Academic Press, New York, pp 183–217
[23] Rose D, Tarjan RE, Lueker G (1976) Algorithmic aspects of vertex elimination on graphs. SIAM J Comput 5:266–283 · Zbl 0353.65019 · doi:10.1137/0205021
[24] Spinrad JP (1993) Doubly lexical ordering of dense 0–1 matrices. Inf Process Lett 45:229–235 · Zbl 0771.68068 · doi:10.1016/0020-0190(93)90209-R
[25] Sritharan R (2008) Chordal bipartite completion of colored graphs. Discrete Math 308:2581–2588 · Zbl 1147.05034 · doi:10.1016/j.disc.2007.06.004
[26] Yannakakis M (1981) Computing the minimum fill-in is NP-complete. SIAM J Algebraic Discrete Methods 2:77–79 · Zbl 0496.68033 · doi:10.1137/0602010
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.