Cited By
View all- Conrado GGoharshady ALam C(2023)The Bounded Pathwidth of Control-Flow GraphsProceedings of the ACM on Programming Languages10.1145/36228077:OOPSLA2(292-317)Online publication date: 16-Oct-2023
Fully Polynomial-Time Distributed Computation in Low-Treewidth Graphs
Pages 11 - 22
Abstract
We consider global problems, i.e. problems that take at least diameter time, even when the bandwidth is not restricted. We show that all problems considered admit efficient solutions in low-treewidth graphs.
References
[1]
Amir Abboud, Keren Censor-Hillel, and Seri Khoury. 2016. Near-Linear Lower Bounds for Distributed Distance Computations, Even in Sparse Networks. In 30th International Symposium on Distributed Computing (DISC). 29--42.
[2]
Udit Agarwal, Vijaya Ramachandran, Valerie King, and Matteo Pontecorvi. 2018. A Deterministic Distributed Algorithm for Exact Weighted All-Pairs Shortest Paths in Õ(n 3/2 ) Rounds. In Proc. of the 2018 ACM Symposium on Principles of Distributed Computing (PODC). 199--205.
[3]
Mohamad Ahmadi and Fabian Kuhn. 2020. Distributed maximum matching verification in CONGEST. In 34th International Symposium on Distributed Computing (DISC). 37:1--37:18. https://doi.org/10.4230/LIPIcs.DISC.2020.37
[4]
Mohamad Ahmadi, Fabian Kuhn, and Rotem Oshman. 2018. Distributed approximate maximum matching in the congest model. In Proceedings of the 32rd International Symposium on Distributed Computing (DISC). 6:1--6:17. https: //doi.org/10.4230/LIPIcs.DISC.2018.6
[5]
Nir Bacrach, Keren Censor-Hillel, Michal Dory, Yuval Efron, Dean Leitersdorf, and Ami Paz. 2019. Hardness of Distributed Optimization. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (PODC). 238--247. https://doi.org/10.1145/3293611.3331597
[6]
Reuven Bar-Yehuda, Keren Censor-Hillel, Mohsen Ghaffari, and Gregory Schwartzman. 2017. Distributed approximation of maximum independent set and maximum matching. In Proceedings of the 36th annual ACM Symposium on Principles of Distributed Computing (PODC). 165--174. https://doi.org/10.1145/ 3087801.3087806
[7]
Ruben Becker, Andreas Karrenbauer, Sebastian Krinninger, and Christoph Lenzen. 2017. Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models. In 31st International Symposium on Distributed Computing (DISC). 7:1--7:16.
[8]
Ran Ben-Basat, Ken-ichi Kawarabayashi, and Gregory Schwartzman. 2019. Parameterized Distributed Algorithms. In Proc. of 33rd International Symposium on Distributed Computing (DISC). 6:1--6:16. https://doi.org/10.4230/LIPIcs.DISC.2019.6
[9]
Aaron Bernstein and Danupon Nanongkai. 2019. Distributed Exact Weighted All-Pairs Shortest Paths in near-Linear Time. In Proc. of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC). 334--342. https://doi.org/10. 1145/3313276.3316326
[10]
Keren Censor-Hillel, Orr Fischer, Tzlil Gonen, François Le Gall, Dean Leitersdorf, and Rotem Oshman. 2020. Fast Distributed Algorithms for Girth, Cycles and Small Subgraphs. In Proc. of 34th International Symposium on Distributed Computing (DISC). 33:1--33:17. https://doi.org/10.4230/LIPIcs.DISC.2020.33
[11]
Shiri Chechik and Doron Mukhtar. 2020. Single-Source Shortest Paths in the CONGEST Model with Improved Bound. In Proceedings of the 39th Symposium on Principles of Distributed Computing. 464--473. https://doi.org/10.1145/3382734. 3405729
[12]
Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Micha? Pilipczuk, and Saket Saurabh. 2015. Parameterized algorithms. Springer. https://doi.org/10.1007/978--3--319--21275--3
[13]
Atish Das Sarma, Michael Dinitz, and Gopal Pandurangan. 2012. Efficient Computation of Distance Sketches in Distributed Networks. In Proc. of the 24th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 318--326.
[14]
Atish Das Sarma, Stephan Holzer, Liah Kor, Amos Korman, Danupon Nanongkai, Gopal Pandurangan, David Peleg, and Roger Wattenhofer. 2011. Distributed Verification and Hardness of Distributed Approximation. In Proc. of the 43rd Annual ACM Symposium on Theory of Computing. 363--372.
[15]
Michael Elkin. 2017. Distributed exact shortest paths in sublinear time. In Proc. of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC). 757--770.
[16]
Fedor V. Fomin, Daniel Lokshtanov, Michal Pilipczuk, Saket Saurabh, and Marcin Wrochna. 2017. Fully Polynomial-Time Parameterized Computations for Graphs and Matrices of Low Treewidth. ACM Transactions on Algorithms 14, 3 (2017), 1419--1432. https://doi.org/10.1145/3186898
[17]
Sebastian Forster and Danupon Nanongkai. 2018. A Faster Distributed Single- Source Shortest Paths Algorithm. In 59th IEEE Annual Symposium on Foundations of Computer Science (FOCS). 686--697.
[18]
Ofer Freedman, Pawel Gawrychowski, Patrick K. Nicholson, and Oren Weimann. 2017. Optimal Distance Labeling Schemes for Trees. In Proc. of the ACM Symposium on Principles of Distributed Computing (PODC). 185--194.
[19]
Silvio Frischknecht, Stephan Holzer, and Roger Wattenhofer. 2012. Networks Cannot Compute Their Diameter in Sublinear Time. In Proc. of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 1150--1162.
[20]
Cyril Gavoille and Christophe Paul. 2003. Distance Labeling Scheme and Split Decomposition. Discrete Mathematics 273 (12 2003), 115--130.
[21]
C. Gavoille and C. Paul. 2008. Optimal Distance Labeling for Interval Graphs and Related Graph Families. SIAM Journal on Discrete Mathematics 22, 3 (2008), 1239--1258.
[22]
Cyril Gavoille, David Peleg, Stéphane Pérennes, and Ran Raz. 2004. Distance labeling in graphs. Journal of Algorithms 53, 1 (2004), 85--112. https://doi.org/10. 1016/j.jalgor.2004.05.002
[23]
Mohsen Ghaffari and Bernhard Haeupler. 2016. Distributed Algorithms for Planar Networks I: Planar Embedding. In Proc. of the 48th ACM Symposium on Principles of Distributed Computing (PODC). 29--38.
[24]
Mohsen Ghaffari and Bernhard Haeupler. 2016. Distributed Algorithms for Planar Networks II: Low-congestion Shortcuts, MST, and Min-Cut. In Proc. of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 202--219.
[25]
Mohsen Ghaffari and Jason Li. 2018. Improved Distributed Algorithms for Exact Shortest Paths. In Proc. of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC). 431--444.
[26]
Mohsen Ghaffari and Merav Parter. 2017. Near-Optimal Distributed DFS in Planar Graphs. In 31st International Symposium on Distributed Computing (DISC 2017), Vol. 91. 21:1--21:16. https://doi.org/10.4230/LIPIcs.DISC.2017.21
[27]
Ofer Grossman, Seri Khoury, and Ami Paz. 2020. Improved Hardness of Approximation of Diameter in the CONGEST Model. In Proc. of 34th International Symposium on Distributed Computing (DISC). 19:1--19:16. https://doi.org/10.4230/ LIPIcs.DISC.2020.19
[28]
Bernhard Haeupler, D. Ellis Hershkowitz, and David Wajc. 2018. Round- and Message-Optimal Distributed Graph Algorithms. In Proc. of the 2018 ACM Symposium on Principles of Distributed Computing (PODC). 119--128. https: //doi.org/10.1145/3212734.3212737
[29]
Bernhard Haeupler, Taisuke Izumi, and Goran Zuzic. 2016. Near-Optimal Low- Congestion Shortcuts on Bounded Parameter Graphs. In Proc. of 30th International Symposium on Distributed Computing (DISC). 158--172.
[30]
Bernhard Haeupler and Jason Li. 2018. Faster Distributed Shortest Path Approximations via Shortcuts. In Proc. of 32nd International Symposium on Distributed Computing (DISC). 33:1--33:14.
[31]
Bernhard Haeupler, Jason Li, and Goran Zuzic. 2018. Minor Excluded Network Families Admit Fast Distributed Algorithms. In Proc. of the 2018 ACM Symposium on Principles of Distributed Computing, (PODC). 465--474.
[32]
Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. 2016. A Deterministic Almost-tight Distributed Algorithm for Approximating Singlesource Shortest Paths. In Proc. of the 48th Annual ACM Symposium on Theory of Computing (STOC). 489--498.
[33]
Stephan Holzer and Roger Wattenhofer. 2012. Optimal Distributed All Pairs Shortest Paths and Applications. In Proc. of the 2012 ACM Symposium on Principles of Distributed Computing (PODC). 355--364.
[34]
Chien-Chung Huang, Danupon Nanongkai, and Thatchaphol Saranurak. 2017. Distributed Exact Weighted All-Pairs Shortest Paths in 5/4) Rounds. In 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS). 168--179.
[35]
Yoichi Iwata, Tomoaki Ogasawara, and Naoto Ohsaka. 2018. On the Power of Tree-Depth for Fully Polynomial FPT Algorithms. In Proc. of 35th Symposium on Theoretical Aspects of Computer Science (STACS), Vol. 96. 41:1--41:14. https: //doi.org/10.4230/LIPIcs.STACS.2018.41
[36]
Taisuke Izumi and Roger Wattenhofer. 2014. Time Lower Bounds for Distributed Distance Oracles. In Proc. of 18th International Conference on Principles of Distributed Systems (OPODIS). 60--75.
[37]
Michal Katz, Nir A. Katz, and David Peleg. 2005. Distance Labeling Schemes for Well-separated Graph Classes. Discrete Applied Mathematics 145, 3 (2005), 384--402.
[38]
Naoki Kitamura and Taisuke Izumi. 2022. A Subquadratic-Time Distributed Algorithm for Exact Maximum Matching. IEICE Transactions on Information and Systems 105, 3 (2022), 634--645. https://doi.org/10.1587/transinf.2021edp7083
[39]
Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer. 2006. The price of being near-sighted. In Proceedings of the seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 1109557--1109666. https://doi.org/10.5555/ 1109557.1109666
[40]
Christoph Lenzen and Boaz Patt-Shamir. 2013. Fast Routing Table Construction Using Small Messages: Extended Abstract. In Proc. of the 45th Annual ACM Symposium on Symposium on Theory of Computing (STOC). 381--390.
[41]
Christoph Lenzen and Boaz Patt-Shamir. 2015. Fast Partial Distance Estimation and Applications. In Proc. of the 2015 ACM Symposium on Principles of Distributed Computing (PODC). 153--162.
[42]
Christoph Lenzen and David Peleg. 2013. Efficient Distributed Source Detection with Limited Bandwidth. In Proc. of the 2013 ACM Symposium on Principles of Distributed Computing (PODC). 375--382.
[43]
Jason Li. 2018. Distributed Treewidth Computation. arXiv (2018). arXiv:1805.10708
[44]
Jason Li and Merav Parter. 2019. Planar Diameter via Metric Compression. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC). 152--163. https://doi.org/10.1145/3313276.3316358
[45]
Zvi Lotker, Boaz Patt-Shamir, and Seth Pettie. 2015. Improved distributed approximate matching. Journal of the ACM (JACM) 62, 5 (2015), 1--17. https: //doi.org/10.1145/2786753
[46]
Silviu Maniu, Pierre Senellart, and Suraj Jog. 2019. An Experimental Study of the Treewidth of Real-World Graph Data. In ICDT (LIPIcs, Vol. 127). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 12:1--12:18.
[47]
Danupon Nanongkai. 2014. Distributed Approximation Algorithms forWeighted Shortest Paths. In Proc. of the 46th Annual ACM Symposium on Theory of Computing (STOC). 565--573.
[48]
Merav Parter. 2020. Distributed Planar Reachability in Nearly Optimal Time. In Proc. of 34th International Symposium on Distributed Computing (DISC). 38:1--38:17. https://doi.org/10.4230/LIPIcs.DISC.2020.38
[49]
David Peleg, Liam Roditty, and Elad Tal. 2012. Distributed Algorithms for Network Diameter and Girth. In Proc. of the 39th International Colloquium Conference on Automata, Languages, and Programming (ICALP). 660--672.
[50]
Goran Zuzic, Gramoz Goranci, Mingquan Ye, Bernhard Haeupler, and Xiaorui Sun. 2022. Universally-Optimal Distributed Shortest Paths and Transshipment via Graph-Based "1-Oblivious Routing. In Proceedings of the 2022 Annual ACMSIAM Symposium on Discrete Algorithms (SODA). 2549--2579. https://doi.org/10. 1137/1.9781611977073.100
Index Terms
- Fully Polynomial-Time Distributed Computation in Low-Treewidth Graphs
Recommendations
Minimum fill-in and treewidth of split+ke and split+kv graphs
In this paper we investigate how graph problems that are NP-hard in general, but polynomial time solvable on split graphs, behave on input graphs that are close to being split. For this purpose we define split+ke and split+kv graphs to be the graphs ...
Restricted space algorithms for isomorphism on bounded treewidth graphs
The Graph Isomorphism problem restricted to graphs of bounded treewidth or bounded tree distance width are known to be solvable in polynomial time. We give restricted space algorithms for these problems proving the following results:*Isomorphism for ...
Hitting forbidden subgraphs in graphs of bounded treewidth
We study the complexity of a generic hitting problem H-Subgraph Hitting, where given a fixed pattern graph H and an input graph G, the task is to find a set XV(G) of minimum size that hits all subgraphs of G isomorphic to H. In the colorful variant of ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
July 2022
464 pages
ISBN:9781450391467
DOI:10.1145/3490148
- General Chair:
- Kunal Agrawal,
- Program Chair:
- I-Ting Angelina Lee
Copyright © 2022 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Sponsors
- SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
- SIGARCH: ACM Special Interest Group on Computer Architecture
- EATCS: European Association for Theoretical Computer Science
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 11 July 2022
Check for updates
Author Tags
Qualifiers
- Research-article
Conference
SPAA '22: 34th ACM Symposium on Parallelism in Algorithms and Architectures
July 11 - 14, 2022
PA, Philadelphia, USA
Acceptance Rates
Overall Acceptance Rate 447 of 1,461 submissions, 31%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 290Total Downloads
- Downloads (Last 12 months)105
- Downloads (Last 6 weeks)19
Reflects downloads up to 30 Sep 2024
Other Metrics
Citations
Cited By
View all- Conrado GGoharshady ALam C(2023)The Bounded Pathwidth of Control-Flow GraphsProceedings of the ACM on Programming Languages10.1145/36228077:OOPSLA2(292-317)Online publication date: 16-Oct-2023
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in