Brief Announcement: Distributed Model Checking on Graphs of Bounded Treedepth
Authors: 
Fedor V. Fomin, Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport, Ioan TodincaAuthors Info & Claims
Pages 205 - 208
Abstract
We establish that every monadic second-order logic (MSO) formula on graphs with bounded treedepth is decidable in a constant number of rounds within the CONGEST model. To our knowledge, this marks the first meta-theorem regarding distributed model-checking. Various optimization problems on graphs are expressible in MSO. Examples include determining whether a graph G has a clique of size k, whether it admits a coloring with k colors, whether it contains a graph H as a subgraph or minor, or whether terminal vertices in G could be connected via vertex-disjoint paths. Our meta-theorem significantly enhances the work of Bousquet et al. [PODC 2022], which was focused on distributed certification of MSO on graphs with bounded treedepth. Moreover, our results can be extended to solving optimization and counting problems expressible in MSO, in graphs of bounded treedepth.
References
[1]
Nicolas Bousquet, Laurent Feuilloley, and Théo Pierron. 2021. Local Certification of Graph Decompositions and Applications to Minor-Free Classes. In 25th International Conference on Principles of Distributed Systems (OPODIS) (LIPIcs, Vol. 217). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 22:1--22:17.
[2]
Keren Censor-Hillel, Ami Paz, and Mor Perry. 2020. Approximate proof-labeling schemes. Theor. Comput. Sci. 811 (2020), 112--124.
[3]
Bruno Courcelle. 1990. The Monadic Second-Order Logic of Graphs. I. Recognizable Sets of Finite Graphs. Inf. Comput. 85, 1 (1990), 12--75.
[4]
Andrew Drucker, Fabian Kuhn, and Rotem Oshman. 2014. On the power of the congested clique model. In 33rd ACM Symposium on Principles of Distributed Computing (PODC). 367--376.
[5]
Michael Elberfeld, Martin Grohe, and Till Tantau. 2016. Where First-Order and Monadic Second-Order Logic Coincide. ACM Trans. Comput. Log. 17, 4 (2016), 25.
[6]
Louis Esperet and Benjamin Lévěque. 2022. Local certification of graphs on surfaces. Theor. Comput. Sci. 909 (2022), 68--75.
[7]
Laurent Feuilloley, Nicolas Bousquet, and Théo Pierron. 2022. What Can Be Certified Compactly? Compact local certification of MSO properties in tree-like graphs. In 41st ACM Symposium on Principles of Distributed Computing (PODC). 131--140.
[8]
Laurent Feuilloley, Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport, Éric Rémila, and Ioan Todinca. 2021. Compact Distributed Certification of Planar Graphs. Algorithmica 83, 7 (2021), 2215--2244.
[9]
Laurent Feuilloley, Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport, Éric Rémila, and Ioan Todinca. 2023. Local certification of graphs with bounded genus. Discret. Appl. Math. 325 (2023), 9--36.
[10]
Pierre Fraigniaud, Frédéric Mazoit, Pedro Montealegre, Ivan Rapaport, and Ioan Todinca. 2023. Distributed Certification for Classes of Dense Graphs. In 37th International Symposium on Distributed Computing (DISC) (LIPIcs, Vol. 281). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 20:1--20:17.
[11]
Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport, and Ioan Todinca. 2024. A Meta-Theorem for Distributed Certification. Algorithmica 86, 2 (2024), 585--612.
[12]
Jakub Gajarský and Petr Hlinený. 2015. Kernelizing MSO Properties of Trees of Fixed Height, and Some Consequences. Log. Methods Comput. Sci. 11, 1 (2015), 1--26.
[13]
Mika Göös and Jukka Suomela. 2016. Locally Checkable Proofs in Distributed Computing. Theory Comput. 12, 1 (2016), 1--33.
[14]
Martin Grohe and Stephan Kreutzer. 2009. Methods for Algorithmic Meta Theorems. In Model Theoretic Methods in Finite Combinatorics - AMS-ASL Joint Special Session, Vol. 558. AMS, 181--206. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.395.8282&rep=rep1&type=pdf
[15]
Amos Korman, Shay Kutten, and David Peleg. 2010. Proof labeling schemes. Distributed Comput. 22, 4 (2010), 215--233.
[16]
Jaroslav Nešetřil and Patrice Ossona de Mendez. 2012. Sparsity - Graphs, Structures, and Algorithms. Algorithms and combinatorics, Vol. 28. Springer.
[17]
Jaroslav Nešetřil and Patrice Ossona de Mendez. 2016. A distributed low tree-depth decomposition algorithm for bounded expansion classes. Distributed Comput. 29, 1 (2016), 39--49.
Index Terms
- Brief Announcement: Distributed Model Checking on Graphs of Bounded Treedepth
Recommendations
Exploring the gap between treedepth and vertex cover through vertex integrity
AbstractFor problems intractable on graphs of bounded treewidth, two graph parameters treedepth and vertex cover number have been used to obtain fine-grained algorithmic and complexity results. Although the studies in this direction are ...
How Much Does a Treedepth Modulator Help to Obtain Polynomial Kernels Beyond Sparse Graphs?
AbstractIn the last years, kernelization with structural parameters has been an active area of research within the field of parameterized complexity. As a relevant example, Gajarský et al. (J Comput Syst Sci 84:219–242, 2017) proved that every graph ...
On the Lossy Kernelization for Connected Treedepth Deletion Set
Graph-Theoretic Concepts in Computer ScienceAbstractWe study the Connected-Treedepth Deletion problem, where the input instance is an undirected graph G, and an integer k and the objective is to decide whether there is a vertex set such that , every connected component of has treedepth at most ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
June 2024
570 pages
ISBN:9798400706684
DOI:10.1145/3662158
- Chair:
- Ran Gelles,
- Proceedings Chair:
- Dennis Olivetti,
- Program Chair:
- Petr Kuznetsov
Copyright © 2024 Copyright is held by the owner/author(s). Publication rights licensed to 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 the author(s) 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
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 17 June 2024
Check for updates
Author Tags
Qualifiers
- Short-paper
Conference
Acceptance Rates
Overall Acceptance Rate 740 of 2,477 submissions, 30%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 26Total Downloads
- Downloads (Last 12 months)26
- Downloads (Last 6 weeks)2
Reflects downloads up to 17 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in