Tight approximation algorithms for bichromatic graph diameter and related problems. (English) Zbl 07561540
Baier, Christel (ed.) et al., 46th international colloquium on automata, languages, and programming, ICALP 2019, Patras, Greece, July 9–12, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 132, Article 47, 15 p. (2019).
Summary: Some of the most fundamental and well-studied graph parameters are the Diameter (the largest shortest paths distance) and Radius (the smallest distance for which a “center” node can reach all other nodes). The natural and important \(ST\)-variant considers two subsets \(S\) and \(T\) of the vertex set and lets the \(ST\)-diameter be the maximum distance between a node in \(S\) and a node in \(T\), and the \(ST\)-radius be the minimum distance for a node of \(S\) to reach all nodes of \(T\). The bichromatic variant is the special case in which \(S\) and \(T\) partition the vertex set.
In this paper we present a comprehensive study of the approximability of \(ST\) and Bichromatic Diameter, Radius, and Eccentricities, and variants, in graphs with and without directions and weights. We give the first nontrivial approximation algorithms for most of these problems, including time/accuracy trade-off upper and lower bounds. We show that nearly all of our obtained bounds are tight under the Strong Exponential Time Hypothesis (SETH), or the related Hitting Set Hypothesis.
For instance, for Bichromatic Diameter in undirected weighted graphs with m edges, we present an \(\widetilde{O}(m^{3/2})\) time \(5/3\)-approximation algorithm, and show that under SETH, neither the running time, nor the approximation factor can be significantly improved while keeping the other unchanged.
For the entire collection see [Zbl 1414.68003].
In this paper we present a comprehensive study of the approximability of \(ST\) and Bichromatic Diameter, Radius, and Eccentricities, and variants, in graphs with and without directions and weights. We give the first nontrivial approximation algorithms for most of these problems, including time/accuracy trade-off upper and lower bounds. We show that nearly all of our obtained bounds are tight under the Strong Exponential Time Hypothesis (SETH), or the related Hitting Set Hypothesis.
For instance, for Bichromatic Diameter in undirected weighted graphs with m edges, we present an \(\widetilde{O}(m^{3/2})\) time \(5/3\)-approximation algorithm, and show that under SETH, neither the running time, nor the approximation factor can be significantly improved while keeping the other unchanged.
For the entire collection see [Zbl 1414.68003].
References:
| [1] | If the k-OV instance has a solution, then there exists a pair of vertices u ∈ S and v ∈ T such that d(u, v) ≥ 4k − 3. |
| [2] | Proof. Construction of the graph. We begin with the k-OV-graph from Theorem 8. Additionally, we add k − 1 new layers of vertices L k+1 , . . . , L 2k−1 , where each new layer contains n k−1 vertices and is connected to the previous layer by a matching. That is, each new layer contains one vertex for every tuple (a 1 , . . . , a k−1 ) where a i ∈ W i for all i, and each (a 1 , . . . , a k−1 ) ∈ L j is connected to its counterpart (a 1 , . . . , a k−1 ) ∈ L j−1 by an edge, for all j. We let S = L 0 and we let T contain the rest of the vertices in the graph. |
| [3] | Correctness of the construction. Case 1: The k-OV instance has no solution. By property 3 of Theorem 8 for all u ∈ S and v ∈ L k , d(u, v) = k. Then, since L k , . . . , L 2k−1 form a series of matchings, for all u ∈ S and v ∈ L k+1 ∪ • • • ∪ L 2k−1 , d(u, v) ≤ 2k − 1. Furthermore, property 5 of Theorem 8 implies that for all u ∈ S and v ∈ L 1 ∪ • • • ∪ L k−1 , d(u, v) ≤ 2k − 1. Thus, we have shown that for all u ∈ S and v ∈ T we have d(u, v) ≤ 2k − 1. |
| [4] | Case 2: The k-OV instance has a solution. Let (a 0 , a 1 , . . . , a k−1 ) be a solution to the k-OV instance where a i ∈ W i for all i. We claim that d((a 0 , . . . , a k−2 ) ∈ S, (a 1 , . . . , a k−1 ) ∈ L 2k−1 )) ≥ 4k − 3. Since L k , . . . , L 2k−1 form a series of matchings, every path from (a 0 , . . . , a k−2 ) ∈ S to (a 1 , . . . , a k−1 ) ∈ L 2k−1 contains the vertex (a 1 , . . . , a k−1 ) ∈ L k . By property 4 of Theorem 8, d((a 0 , . . . , a k−2 ) ∈ S, (a 1 , . . . , a k−1 ) ∈ L k ) ≥ 3k − 2. Thus, d((a 0 , . . . , a k−2 ) ∈ S, (a 1 , . . . , a k−1 ) ∈ L 2k−1 )) ≥ 4k − 3. |
| [5] | Amir Abboud, Virginia Vassilevska Williams, and Joshua R. Wang. Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 377-391, 2016. · Zbl 1410.68392 |
| [6] | Pankaj K. Agarwal, Herbert Edelsbrunner, Otfried Schwarzkopf, and Emo Welzl. Euclidean Minimum Spanning Trees and Bichromatic Closest Pairs. Discrete Comput. Geom., 6(1):407-422, December 1991. · Zbl 0753.68089 |
| [7] | D. Aingworth, C. Chekuri, P. Indyk, and R. Motwani. Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication). SIAM Journal on Computing, 28(4):1167-1181, 1999. · Zbl 0926.68093 |
| [8] | Arturs Backurs, Liam Roditty, Gilad Segal, Virginia Vassilevska Williams, and Nicole Wein. Towards Tight Approximation Bounds for Graph Diameter and Eccentricities. In Proceedings of STOC’18, page to appear, 2018. · Zbl 1427.68225 |
| [9] | Massimo Cairo, Roberto Grossi, and Romeo Rizzi. New Bounds for Approximating Extremal Distances in Undirected Graphs. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 363-376, 2016. · Zbl 1410.68396 |
| [10] | T. M. Chan. More Algorithms for All-Pairs Shortest Paths in Weighted Graphs. In Proc. STOC, pages 590-598, 2007. · Zbl 1231.05245 |
| [11] | Bernard Chazelle, Herbert Edelsbrunner, Leonidas J Guibas, and Micha Sharir. Algorithms for bichromatic line-segment problems and polyhedral terrains. Algorithmica, 11(2):116-132, 1994. · Zbl 0818.68140 |
| [12] | Shiri Chechik, Daniel H. Larkin, Liam Roditty, Grant Schoenebeck, Robert Endre Tarjan, and Virginia Vassilevska Williams. Better Approximation Algorithms for the Graph Diameter. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 1041-1052, 2014. · Zbl 1421.68199 |
| [13] | Don Coppersmith and Michael Elkin. Sparse sourcewise and pairwise distance preservers. SIAM Journal on Discrete Mathematics, 20(2):463-501, 2006. · Zbl 1118.05025 |
| [14] | Pierluigi Crescenzi, Roberto Grossi, Leonardo Lanzi, and Andrea Marino. On Computing the Diameter of Real-World Directed (Weighted) Graphs. In Ralf Klasing, editor, Experimental Algorithms: 11th International Symposium, SEA 2012, Bordeaux, France, June 7-9, 2012. Proceedings, pages 99-110, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg. |
| [15] | Marek Cygan, Fabrizio Grandoni, and Telikepalli Kavitha. On pairwise spanners. arXiv preprint, 2013. arXiv:1301.1999. · Zbl 1354.05131 |
| [16] | Adrian Dumitrescu and Sumanta Guha. Extreme Distances in Multicolored Point Sets. J. Graph Algorithms and Applications, 8(1):27-38, 2004. · Zbl 1068.68101 |
| [17] | Jiawei Gao, Russell Impagliazzo, Antonina Kolokolova, and R. Ryan Williams. Completeness for First-Order Properties on Sparse Structures with Algorithmic Applications. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 2162-2181, 2017. · Zbl 1407.68220 |
| [18] | R. Impagliazzo and R. Paturi. On the Complexity of k-SAT. J. Comput. Syst. Sci., 62(2):367-375, 2001. · Zbl 0990.68079 |
| [19] | Piotr Indyk. A near linear time constant factor approximation for Euclidean bichromatic matching (cost). In SODA, volume 7, pages 39-42, 2007. · Zbl 1302.68290 |
| [20] | Naoki Katoh and Kazuo Iwano. Finding K Farthest Pairs and K Closest/Farthest Bichromatic Pairs for Points in the Plane. In Proceedings of the Eighth Annual Symposium on Computational Geometry, SCG ’92, pages 320-329, 1992. · Zbl 0818.68141 |
| [21] | Telikepalli Kavitha. New pairwise spanners. Theory of Computing Systems, 61(4):1011-1036, 2017. · Zbl 1386.05185 |
| [22] | Philip N Klein. A subset spanner for planar graphs, with application to subset TSP. In Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, pages 749-756. ACM, 2006. · Zbl 1301.05335 |
| [23] | Clémence Magnien, Matthieu Latapy, and Michel Habib. Fast Computation of Empirically Tight Bounds for the Diameter of Massive Graphs. J. Exp. Algorithmics, 13:10:1.10-10:1.9, February 2009. · Zbl 1284.05300 |
| [24] | David Peleg, Liam Roditty, and Elad Tal. Distributed Algorithms for Network Diameter and Girth. In Automata, Languages, and Programming: 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part II, pages 660-672, 2012. · Zbl 1343.68283 |
| [25] | S. Pettie. A new approach to all-pairs shortest paths on real-weighted graphs. Theor. Comput. Sci., 312(1):47-74, 2004. · Zbl 1071.68084 |
| [26] | Seth Pettie and Vijaya Ramachandran. A Shortest Path Algorithm for Real-Weighted Undirected Graphs. SIAM J. Comput., 34(6):1398-1431, 2005. · Zbl 1078.05080 |
| [27] | Liam Roditty and Virginia Vassilevska Williams. Fast approximation algorithms for the diameter and radius of sparse graphs. In Proceedings of the 45th annual ACM symposium on Symposium on theory of computing, STOC ’13, pages 515-524, New York, NY, USA, 2013. ACM. doi:10.1145/2488608.2488673. · Zbl 1293.05184 · doi:10.1145/2488608.2488673 |
| [28] | Frank W. Takes and Walter A. Kosters. Determining the Diameter of Small World Networks. In Proceedings of the 20th ACM International Conference on Information and Knowledge Management, CIKM ’11, pages 1191-1196, 2011. |
| [29] | Virginia Vassilevska Williams. Hardness of Easy Problems: Basing Hardness on Popular Con-jectures such as the Strong Exponential Time Hypothesis (Invited Talk). In 10th International Symposium on Parameterized and Exact Computation, IPEC 2015, September 16-18, 2015, Patras, Greece, pages 17-29, 2015. · Zbl 1378.68054 |
| [30] | R. Williams. A new algorithm for optimal 2-constraint satisfaction and its implications. Theor. Comput. Sci., 348(2-3):357-365, 2005. · Zbl 1081.68095 |
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.
