Document Open Access Logo

Beyond Distributed Subgraph Detection: Induced Subgraphs, Multicolored Problems and Graph Parameters

Authors Amir Nikabadi, Janne H. Korhonen

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2021.15.pdf
  • Filesize: 0.75 MB
  • 18 pages

Document Identifiers

Author Details

Amir Nikabadi
  • ENS de Lyon, France
Janne H. Korhonen
  • IST Austria, Klosterneuburg, Austria

Funding

  • Nikabadi, Amir: Supported by the LABEX MILYON (ANR-10-LABX-0070) of Université de Lyon, within the program "Investissements d'Avenir" (ANR-11-IDEX-0007) operated by the French National Research Agency (ANR).
  • Korhonen, Janne H.: Supported by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 805223 ScaleML).

Acknowledgements

We thank François Le Gall and Masayuki Miyamoto for sharing their work on lower bounds for induced subgraph detection [Le Gall and Miyamoto, 2021].

Cite As Get BibTex

Amir Nikabadi and Janne H. Korhonen. Beyond Distributed Subgraph Detection: Induced Subgraphs, Multicolored Problems and Graph Parameters. In 25th International Conference on Principles of Distributed Systems (OPODIS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 217, pp. 15:1-15:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.OPODIS.2021.15

Abstract

Subgraph detection has recently been one of the most studied problems in the CONGEST model of distributed computing. In this work, we study the distributed complexity of problems closely related to subgraph detection, mainly focusing on induced subgraph detection. The main line of this work presents lower bounds and parameterized algorithms w.r.t structural parameters of the input graph:  
- On general graphs, we give unconditional lower bounds for induced detection of cycles and patterns of treewidth 2 in CONGEST. Moreover, by adapting reductions from centralized parameterized complexity, we prove lower bounds in CONGEST for detecting patterns with a 4-clique, and for induced path detection conditional on the hardness of triangle detection in the congested clique. 
- On graphs of bounded degeneracy, we show that induced paths can be detected fast in CONGEST using techniques from parameterized algorithms, while detecting cycles and patterns of treewidth 2 is hard. 
- On graphs of bounded vertex cover number, we show that induced subgraph detection is easy in CONGEST for any pattern graph. More specifically, we adapt a centralized parameterized algorithm for a more general maximum common induced subgraph detection problem to the distributed setting.  In addition to these induced subgraph detection results, we study various related problems in the CONGEST and congested clique models, including for multicolored versions of subgraph-detection-like problems.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
  • Theory of computation → Computational complexity and cryptography
Keywords
  • distributed algorithms
  • parameterized distributed complexity
  • CONGEST model
  • induced subgraph detection
  • graph parameters
  • lower bounds

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Amir Abboud, Keren Censor-Hillel, and Seri Khoury. Near-linear lower bounds for distributed distance computations, even in sparse networks. In Proc. 30th International Symposium on Distributed Computing (DISC 2016), 2016. URL: https://doi.org/10.1007/978-3-662-53426-7_3.
  2. Faisal N. Abu-Khzam. Maximum common induced subgraph parameterized by vertex cover. Information Processing Letters, 114(3):99-103, 2014. URL: https://doi.org/10.1016/j.ipl.2013.11.007.
  3. Faisal N. Abu-Khzam, Édouard Bonnet, and Florian Sikora. On the complexity of various parameterizations of common induced subgraph isomorphism. Theoretical Computer Science, 697:69-78, 2017. URL: https://doi.org/10.1016/j.tcs.2017.07.010.
  4. Noga Alon and Shai Gutner. Linear time algorithms for finding a dominating set of fixed size in degenerated graphs. In Proc. 13th International Computing and Combinatorics Conference (COCOON 2007), pages 394-405. Springer, 2007. Google Scholar
  5. Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. Journal of the ACM, 42(4):844-856, 1995. URL: https://doi.org/10.1145/210332.210337.
  6. Nir Bacrach, Keren Censor-Hillel, Michal Dory, Yuval Efron, Dean Leitersdorf, and Ami Paz. Hardness of distributed optimization. In Proc. ACM Symposium on Principles of Distributed Computing (PODC 2019), pages 238-247, 2019. Google Scholar
  7. Leonid Barenboim and Michael Elkin. Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition. Distributed Computing, 22(5-6):363-379, 2010. URL: https://doi.org/10.1007/s00446-009-0088-2.
  8. Leonid Barenboim and Michael Elkin. Distributed Graph Coloring: Fundamentals and Recent Developments. Synthesis Lectures on Distributed Computing Theory. Morgan & Claypool, 2013. URL: https://doi.org/10.2200/S00520ED1V01Y201307DCT011.
  9. Leonid Barenboim and Victor Khazanov. Distributed symmetry-breaking algorithms for congested cliques. In International Computer Science Symposium in Russia, pages 41-52. Springer, 2018. Google Scholar
  10. Ran Ben-Basat, Ken ichi Kawarabayashi, and Gregory Schwartzman. Parameterized Distributed Algorithms. In Proc. 33rd International Symposium on Distributed Computing (DISC 2019), 2019. URL: https://doi.org/10.4230/LIPIcs.DISC.2019.6.
  11. Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. Narrow sieves for parameterized paths and packings. Journal of Computer and System Sciences, 87:119-139, 2017. URL: https://doi.org/10.1016/j.jcss.2017.03.003.
  12. Andreas Brandstädt, Van Bang Le, and Jeremy P. Spinrad. Graph classes: a survey. SIAM Monographs on Discrete Mathematics and Applications. Society for Industrial and Applied Mathematics, 1999. Google Scholar
  13. Leizhen Cai, Siu Man Chan, and Siu On Chan. Random separation: A new method for solving fixed-cardinality optimization problems. In Proc. 2nd International Workshop on Parameterized and Exact Computation (IWPEC 2006), pages 239-250. Springer, 2006. Google Scholar
  14. Keren Censor-Hillel, Yi-Jun Chang, François Le Gall, and Dean Leitersdorf. Tight distributed listing of cliques. In Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA 2021), 2021. Google Scholar
  15. Keren Censor-Hillel, Orr Fischer, Tzlil Gonen, François Le Gall, Dean Leitersdorf, and Rotem Oshman. Fast Distributed Algorithms for Girth, Cycles and Small Subgraphs. In Hagit Attiya, editor, Proc. 34th International Symposium on Distributed Computing (DISC 2020), volume 179, 2020. URL: https://doi.org/10.4230/LIPIcs.DISC.2020.33.
  16. Keren Censor-Hillel, Petteri Kaski, Janne H. Korhonen, Christoph Lenzen, Ami Paz, and Jukka Suomela. Algebraic methods in the congested clique. In Proc. ACM Symposium on Principles of Distributed Computing (PODC 2015), pages 143-152, 2015. Google Scholar
  17. Keren Censor-Hillel, Seri Khoury, and Ami Paz. Quadratic and near-quadratic lower bounds for the CONGEST model. In Proc. 31st International Symposium on Distributed Computing (DISC 2017), 2017. URL: https://doi.org/10.4230/LIPIcs.DISC.2017.10.
  18. Yi-Jun Chang and Thatchaphol Saranurak. Improved distributed expander decomposition and nearly optimal triangle enumeration. In Proc. ACM Symposium on Principles of Distributed Computing (PODC 2019), pages 66-73, 2019. Google Scholar
  19. Yijia Chen and Jorg Flum. On parameterized path and chordless path problems. In Proc. 22nd Annual IEEE Conference on Computational Complexity (CCC 2007), pages 250-263, 2007. Google Scholar
  20. Marek Cygan, Fedor V Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized algorithms. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-21275-3.
  21. Artur Czumaj and Christian Konrad. Detecting cliques in congest networks. Distributed Computing, 2019. URL: https://doi.org/10.1007/s00446-019-00368-w.
  22. Mina Dalirrooyfard, Thuy Duong Vuong, and Virginia Vassilevska Williams. Graph pattern detection: Hardness for all induced patterns and faster non-induced cycles. In Proc. 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC 2019), pages 1167-1178, 2019. URL: https://doi.org/10.1145/3313276.3316329.
  23. Danny Dolev, Christoph Lenzen, and Shir Peled. "Tri, tri again": Finding triangles and small subgraphs in a distributed setting. In Proc. 26th International Symposium on Distributed Computing (DISC 2012), pages 195-209, 2012. URL: https://doi.org/10.1007/978-3-642-33651-5_14.
  24. Rod G. Downey and Michael R. Fellows. Fixed-parameter tractability and completeness II: On completeness for W[1]. Theoretical Computer Science, 141(1):109-131, 1995. URL: https://doi.org/10.1016/0304-3975(94)00097-3.
  25. Andrew Drucker, Fabian Kuhn, and Rotem Oshman. On the power of the congested clique model. In Proc. 33rd ACM Symposium on Principles of Distributed Computing (PODC 2014), pages 367-376, 2014. URL: https://doi.org/10.1145/2611462.2611493.
  26. Guy Even, Orr Fischer, Pierre Fraigniaud, Tzlil Gonen, Reut Levi, Moti Medina, Dennis Olivetti Pedro Montealegre, Rotem Oshman, Ivan Rapaport, and Ioan Todinca. Three notes on distributed property testing. In Proc. 31st International Symposium on Distributed Computing (DISC 2017), 2017. Google Scholar
  27. Michael R. Fellows, Danny Hermelin, Frances Rosamond, and Stéphane Vialette. On the parameterized complexity of multiple-interval graph problems. Theoretical Computer Science, 410(1):53-61, 2009. URL: https://doi.org/10.1016/j.tcs.2008.09.065.
  28. Orr Fischer, Tzlil Gonen, Fabian Kuhn, and Rotem Oshman. Possibilities and impossibilities for distributed subgraph detection. In Proc. 30th Symposium on Parallelism in Algorithms and Architectures (SPAA 2018), pages 153-162, 2018. Google Scholar
  29. Pierre Fraigniaud and Dennis Olivetti. Distributed detection of cycles. In Proc. 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2017), pages 153-162, 2017. URL: https://doi.org/10.1145/3087556.3087571.
  30. Silvio Frischknecht, Stephan Holzer, and Roger Wattenhofer. Networks cannot compute their diameter in sublinear time. In Proc. 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012), 2012. Google Scholar
  31. Mohsen Ghaffari and Ali Sayyadi. Distributed arboricity-dependent graph coloring via all-to-all communication. In Proc. 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), 2019. Google Scholar
  32. Janne H. Korhonen and Amir Nikabadi. Beyond distributed subgraph detection: Induced subgraphs, multicolored problems and graph parameters, 2021. URL: http://arxiv.org/abs/2109.06561.
  33. Janne H. Korhonen and Joel Rybicki. Deterministic subgraph detection in broadcast CONGEST. In Proc. 21st International Conference on Principles of Distributed Systems (OPODIS 2017), 2017. URL: https://doi.org/10.4230/LIPIcs.OPODIS.2017.4.
  34. Janne H. Korhonen and Jukka Suomela. Towards a complexity theory for the congested clique. In Proc. 30th on Symposium on Parallelism in Algorithms and Architectures (SPAA 2018), pages 163-172, 2018. Google Scholar
  35. Eyal Kushilevitz and Noam Nisan. Communication complexity. Cambridge University Press, 1997. Google Scholar
  36. François Le Gall and Masayuki Miyamoto. Lower bounds for induced cycle detection in distributed computing. In Proc. 32nd International Symposium on Algorithms and Computation (ISAAC 2021), 2021. URL: http://arxiv.org/abs/2110.00741.
  37. Jason Li. Distributed treewidth computation, 2018. URL: http://arxiv.org/abs/1805.10708.
  38. Burkhard Monien. How to find long paths efficiently. North-Holland Mathematics Studies, 109:239-254, 1985. Google Scholar
  39. Jaroslav Nešetřil and Svatopluk Poljak. On the complexity of the subgraph problem. Commentationes Mathematicae Universitatis Carolinae, 26(2):415-419, 1985. Google Scholar
  40. Krzysztof Pietrzak. On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems. Journal of Computer and System Sciences, 67(4):757-771, 2003. URL: https://doi.org/10.1016/S0022-0000(03)00078-3.
  41. Alexander A. Razborov. On the distributional complexity of disjointness. Theoretical Computer Science, 106(2):385-390, 1992. URL: https://doi.org/10.1016/0304-3975(92)90260-M.
  42. Atish Das Sarma, Stephan Holzer, Liah Kor, Amos Korman, Danupon Nanongkai, Gopal Pandurangan, David Peleg, and Roger Wattenhofer. Distributed verification and hardness of distributed approximation. SIAM Journal on Computing, 41:1235-1265, 2012. URL: https://doi.org/10.1137/11085178X.
  43. Sebastian Siebertz and Alexandre Vigny. Parameterized distributed complexity theory: A logical approach. arXiv preprint, 2019. URL: http://arxiv.org/abs/1903.00505.
  44. Virginia Vassilevska. Efficient algorithms for path problems in weighted graphs. PhD thesis, Carnegie Mellon University, 2008. Google Scholar
  45. Ryan Williams. Finding paths of length k in O^*(2^k) time. Information Processing Letters, 109(6):315-318, 2009. Google Scholar
  46. Raphael Yuster and Uri Zwick. Finding even cycles even faster. SIAM Journal on Discrete Mathematics, 10(2):209-222, 1997. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact