Multi-priority graph sparsification. (English) Zbl 07781720
Hsieh, Sun-Yuan (ed.) et al., Combinatorial algorithms. 34th international workshop, IWOCA 2023, Tainan, Taiwan, June 7–10, 2023. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13889, 1-12 (2023).
Summary: A sparsification of a given graph \(G\) is a sparser graph (typically a subgraph) which aims to approximate or preserve some property of \(G\). Examples of sparsifications include but are not limited to spanning trees, Steiner trees, spanners, emulators, and distance preservers. Each vertex has the same priority in all of these problems. However, real-world graphs typically assign different “priorities” or “levels” to different vertices, in which higher-priority vertices require higher-quality connectivity between them. Multi-priority variants of the Steiner tree problem have been studied previously, but have been much less studied for other types of sparsifiers. In this paper, we define a generalized multi-priority problem and present a rounding-up approach that can be used for a variety of graph sparsifications. Our analysis provides a systematic way to compute approximate solutions to multi-priority variants of a wide range of graph sparsification problems given access to a single-priority subroutine.
For the entire collection see [Zbl 1527.68009].
For the entire collection see [Zbl 1527.68009].
MSC:
| 68Rxx | Discrete mathematics in relation to computer science |
| 68Wxx | Algorithms in computer science |
References:
| [1] | Abboud, A., Bodwin, G.: Lower bound amplification theorems for graph spanners. In: Proceedings of the 27th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 841-856 (2016) · Zbl 1410.68264 |
| [2] | Abboud, A.; Bodwin, G., The 4/3 additive spanner exponent is tight, J. ACM (JACM), 64, 4, 28 (2017) · Zbl 1410.68263 · doi:10.1145/3088511 |
| [3] | Ahmed, A.R., et al.: Multi-level Steiner trees. In: 17th International Symposium on Experimental Algorithms (SEA), pp. 15:1-15:14 (2018). doi:10.4230/LIPIcs.SEA.2018.15 · Zbl 1493.68397 |
| [4] | Ahmed, R.; Bodwin, G.; Hamm, K.; Kobourov, S.; Spence, R.; Kowalik, Ł.; Pilipczuk, M.; Rzążewski, P., On additive spanners in weighted graphs with local error, Graph-Theoretic Concepts in Computer Science, 361-373 (2021), Cham: Springer, Cham · Zbl 07538590 · doi:10.1007/978-3-030-86838-3_28 |
| [5] | Ahmed, R., Graph spanners: a tutorial review, Comput. Sci. Rev., 37 (2020) · Zbl 1478.68206 · doi:10.1016/j.cosrev.2020.100253 |
| [6] | Ahmed, R., Bodwin, G., Sahneh, F.D., Hamm, K., Kobourov, S., Spence, R.: Multi-level weighted additive spanners. In: Coudert, D., Natale, E. (eds.) 19th International Symposium on Experimental Algorithms (SEA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Dagstuhl, Germany, vol. 190, pp. 16:1-16:23. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021). doi:10.4230/LIPIcs.SEA.2021.16. https://drops.dagstuhl.de/opus/volltexte/2021/13788 · Zbl 07538590 |
| [7] | Ahmed, R.; Hamm, K.; Latifi Jebelli, MJ; Kobourov, S.; Sahneh, FD; Spence, R.; Kotsireas, I.; Pardalos, P.; Parsopoulos, KE; Souravlias, D.; Tsokas, A., Approximation algorithms and an integer program for multi-level graph spanners, Analysis of Experimental Algorithms, 541-562 (2019), Cham: Springer, Cham · doi:10.1007/978-3-030-34029-2_35 |
| [8] | Ahmed, R., Hamm, K., Kobourov, S., Jebelli, M.J.L., Sahneh, F.D., Spence, R.: Multi-priority graph sparsification. arXiv preprint arXiv:2301.12563 (2023) · Zbl 07781720 |
| [9] | Aingworth, D.; Chekuri, C.; Indyk, P.; Motwani, R., Fast estimation of diameter and shortest paths (without matrix multiplication), SIAM J. Comput., 28, 1167-1181 (1999) · Zbl 0926.68093 · doi:10.1137/S0097539796303421 |
| [10] | Althöfer, I.; Das, G.; Dobkin, D.; Joseph, D.; Soares, J., On sparse spanners of weighted graphs, Discret. Comput. Geom., 9, 1, 81-100 (1993) · Zbl 0762.05039 · doi:10.1007/BF02189308 |
| [11] | Balakrishnan, A.; Magnanti, TL; Mirchandani, P., Modeling and heuristic worst-case performance analysis of the two-level network design problem, Manag. Sci., 40, 7, 846-867 (1994) · Zbl 0816.90127 · doi:10.1287/mnsc.40.7.846 |
| [12] | Baswana, S.; Kavitha, T.; Mehlhorn, K.; Pettie, S., Additive spanners and \(( \alpha , \beta )\)-spanners, ACM Trans. Algorithms (TALG), 7, 1, 5 (2010) · Zbl 1295.05094 |
| [13] | Bodwin, G., New results on linear size distance preservers, SIAM J. Comput., 50, 2, 662-673 (2021) · Zbl 1519.05062 · doi:10.1137/19M123662X |
| [14] | Byrka, J., Grandoni, F., Rothvoß, T., Sanità, L.: Steiner tree approximation via iterative randomized rounding. J. ACM 60(1), 6:1-6:33 (2013). doi:10.1145/2432622.2432628 · Zbl 1281.68234 |
| [15] | Charikar, M.; Naor, J.; Schieber, B., Resource optimization in QoS multicast routing of real-time multimedia, IEEE/ACM Trans. Netw., 12, 2, 340-348 (2004) · doi:10.1109/TNET.2004.826288 |
| [16] | Chechik, S.: New additive spanners. In: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 498-512. Society for Industrial and Applied Mathematics (2013) · Zbl 1412.68165 |
| [17] | Chechik, S.; Wulff-Nilsen, C., Near-optimal light spanners, ACM Trans. Algorithms (TALG), 14, 3, 33 (2018) · Zbl 1457.05029 |
| [18] | Chuzhoy, J., Gupta, A., Naor, J.S., Sinha, A.: On the approximability of some network design problems. ACM Trans. Algorithms 4(2), 23:1-23:17 (2008). doi:10.1145/1361192.1361200 · Zbl 1445.68156 |
| [19] | Elkin, M., Gitlitz, Y., Neiman, O.: Almost shortest paths and PRAM distance oracles in weighted graphs. arXiv preprint arXiv:1907.11422 (2019) |
| [20] | Elkin, M., Gitlitz, Y., Neiman, O.: Improved weighted additive spanners. arXiv preprint arXiv:2008.09877 (2020) · Zbl 07774272 |
| [21] | Erdős, P.: Extremal problems in graph theory. In: Proceedings of the Symposium on Theory of Graphs and its Applications, p. 2936 (1963) |
| [22] | Hauptmann, M., Karpiński, M.: A compendium on Steiner tree problems. Inst. für Informatik (2013) |
| [23] | Karpinski, M.; Mandoiu, II; Olshevsky, A.; Zelikovsky, A., Improved approximation algorithms for the quality of service multicast tree problem, Algorithmica, 42, 2, 109-120 (2005) · Zbl 1079.68013 · doi:10.1007/s00453-004-1133-y |
| [24] | Kavitha, T., New pairwise spanners, Theory Comput. Syst., 61, 4, 1011-1036 (2016) · Zbl 1386.05185 · doi:10.1007/s00224-016-9736-7 |
| [25] | Klein, P.N.: A subset spanner for planar graphs, with application to subset TSP. In: Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing, STOC 2006, pp. 749-756. ACM, New York (2006). doi:10.1145/1132516.1132620. doi:10.1145/1132516.1132620 · Zbl 1301.05335 |
| [26] | Knudsen, MBT; Ravi, R.; Gørtz, IL, Additive spanners: a simple construction, Algorithm Theory - SWAT 2014, 277-281 (2014), Cham: Springer, Cham · Zbl 1417.05219 · doi:10.1007/978-3-319-08404-6_24 |
| [27] | Laekhanukit, B.; Aceto, L.; Henzinger, M.; Sgall, J., An improved approximation algorithm for minimum-cost subset k-connectivity, Automata, Languages and Programming, 13-24 (2011), Heidelberg: Springer, Heidelberg · Zbl 1332.68287 · doi:10.1007/978-3-642-22006-7_2 |
| [28] | Le, H.: A PTAS for subset TSP in minor-free graphs. In: Proceedings of the Thirty-First Annual. Society for Industrial and Applied Mathematics, USA (2020) · Zbl 07304164 |
| [29] | Nutov, Z.: Approximating minimum cost connectivity problems via uncrossable bifamilies and spider-cover decompositions. In: IEEE 50th Annual Symposium on Foundations of Computer Science (FOCS 2009), Los Alamitos, CA, USA. IEEE Computer Society (2009). doi:10.1109/FOCS.2009.9. doi:10.1109/FOCS.2009.9 · Zbl 1292.68170 |
| [30] | Nutov, Z., Approximating subset k-connectivity problems, J. Discret. Algorithms, 17, 51-59 (2012) · Zbl 1281.68237 · doi:10.1016/j.jda.2012.08.001 |
| [31] | Sahneh, F.D., Kobourov, S., Spence, R.: Approximation algorithms for the priority Steiner tree problem. In: 27th International Computing and Combinatorics Conference (COCOON) (2021). http://arxiv.org/abs/1811.11700 · Zbl 07670456 |
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.
