Restrictions of minimum spanner problems. (English) Zbl 0890.68106

Summary: A \(t\)-spanner of a graph \(G\) is a spanning subgraph \(H\) such that the distance between any two vertices in \(H\) is at most \(t\) times their distance in \(G\). Spanners arise in the context of approximating the original graph with a sparse subgraph [D. Peleg and A. A. Schäffer, J. Graph Theory 13, No. 1, 99-116 (1989; Zbl 0673.05059)]. The MINIMUM \(t\)-SPANNER problem seeks to find a \(t\)-spanner with the minimum number of edges for the given graph. In this paper, we completely settle the complexity status of this problem for various values of \(t\), on chordal graphs, split graphs, bipartite graphs and convex bipartite graphs. Our results settle an open question raised by L. Cai [Discrete Appl. Math. 48, No. 2, 187-194 (1994; Zbl 0788.68057)] and also greatly simplify some of the proofs presented by Cai and by L. Cai and M. Keil [Networks 24, No. 4, 233-249 (1994; Zbl 0821.68091)]. We also give a factor 2 approximation algorithm for the MINIMUM 2-SPANNER problem on interval graphs. Finally, we provide approximation algorithms for the bandwidth minimization problem on convex bipartite graphs and split graphs using the notion of tree spanners.


68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI Link


[1] Althöfer; Das, G.; Dobkin, D.; Joseph, D.; Soares, J., On sparse spanners of weighted graphs, Discrete Comput. Geom., 9, 81-100 (1993) · Zbl 0762.05039
[2] Assmann, S. F.; Peck, G. W.; Syslo, M. M.; Zak, J., The bandwidth of caterpillars with hairs of length 1 and 2, SIAM J. Algebraic Discrete Methods, 2, 387-393 (1981) · Zbl 0494.05059
[3] Awerbuch, B., Complexity of network synchronization, J. Assoc. Comput. Mach., 32, 804-823 (1985) · Zbl 0628.68045
[4] Bandelt, H.; Dress, A., Reconstructing the shape of a tree from observed dissimilarity data, Adv. Appl. Math., 7, 309-343 (1986) · Zbl 0613.62083
[5] Booth, K. S.; Lueker, G. S., Testing for the consecutive ones property, interval graphs and graph planarity using P-Q tree algorithms,, J. Comput. System Sci., 13, 335-379 (1976) · Zbl 0367.68034
[6] Cai, L., Technical Report, 260/92 (1992)
[7] Cai, L., NP-completeness of minimum spanner problems, Discrete Appl. Math., 48, 187-194 (1994) · Zbl 0788.68057
[8] Cai, L.; Keil, M., Spanners in graphs of bounded degree, Networks, 24, 233-249 (1994) · Zbl 0821.68091
[9] Cai, L.; Keil, J. M., Degree-bounded spanners, Parallel Process. Lett., 3, 457-468 (1993)
[11] Garey, M. R.; Graham, R. L.; Johnson, D. S.; Knuth, D. E., Complexity results for bandwidth minimization, SIAM J. Appl. Math., 34, 477-495 (1978) · Zbl 0385.05048
[12] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), Freeman: Freeman San Francisco · Zbl 0411.68039
[13] Gilmore, P. C.; Hoffman, A. J., A characterization of comparability graphs and of interval graphs, Canad. J. Math., 16, 539-548 (1964) · Zbl 0121.26003
[14] Golumbic, M. C., Algorithmic Graph Theory and Perfect Graphs (1980), Academic Press: Academic Press New York · Zbl 0541.05054
[15] Harary, F., Graph Theory (1969), Addison-Wesley: Addison-Wesley Reading · Zbl 0797.05064
[16] Kloks, T.; Kratsch, D.; Müller, H., Approximating the bandwidth for asteroidal triple-free graphs, Algorithms-ESA ’95. Algorithms-ESA ’95, Lecture Notes in Computer Science, 979 (1979), Springer-Verlag: Springer-Verlag Berlin/New York, p. 434-447 · Zbl 1512.68235
[17] Kloks, T.; Kratsch, D.; Müller, H., Forschungsergebnisse Math/95/6 (1995)
[19] Liestman, A. L.; Shermer, T. C., Additive graph spanners, Networks, 23, 343-364 (1993) · Zbl 0783.68094
[20] Liestman, A. L.; Shermer, T. C., Grid spanners, Networks, 23, 123-133 (1993) · Zbl 0777.05077
[21] Madanlal, M. S.; Venkatesan, G.; Pandu Rangan, C., Tree 3-spanners on interval, permutation and regular bipartite graphs, Inform. Process. Lett., 59, 97-102 (1996) · Zbl 0900.68332
[24] Papadimitriou, C. H., TheNP, Computing, 16, 263-270 (1976) · Zbl 0321.65019
[25] Peleg, D.; Schäffer, A. A., Graph spanners, J. Graph Theory, 13, 99-116 (1989) · Zbl 0673.05059
[28] Ramalingam, G.; Pandu Rangan, C., A unified approach to domination problems on interval graphs, Inform. Process. Lett., 27, 271-274 (1988) · Zbl 0658.05040
[29] Sprague, A. P., An \(Onn\), SIAM J. Discrete Math., 7, 213-220 (1994)
[30] Yannakakis, M.; Gavril, F., Edge dominating sets in graphs, SIAM J. Appl. Math., 38, 364-372 (1980) · Zbl 0455.05047
[31] Yannakakis, M., Edge-deletion problems, SIAM J. Comput., 10, 297-309 (1981) · Zbl 0468.05043
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.