Skip to main content
SpringerLink
Log in

Compact Distributed Certification of Planar Graphs

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

Naor M., Parter M., Yogev E.: (The power of distributed verifiers in interactive proofs. In: 31st ACM-SIAM symposium on discrete algorithms (SODA), pp 1096–115, 2020. https://doi.org/10.1137/1.9781611975994.67) have recently demonstrated the existence of a distributed interactive proof for planarity (i.e., for certifying that a network is planar), using a sophisticated generic technique for constructing distributed IP protocols based on sequential IP protocols. The interactive proof for planarity is based on a distributed certification of the correct execution of any given sequential linear-time algorithm for planarity testing. It involves three interactions between the prover and the randomized distributed verifier (i.e., it is a dMAM protocol), and uses small certificates, on \(O(\log n)\) bits in n-node networks. We show that a single interaction with the prover suffices, and randomization is unecessary, by providing an explicit description of a proof-labeling scheme for planarity, still using certificates on just \(O(\log n)\) bits. We also show that there are no proof-labeling schemes—in fact, even no locally checkable proofs—for planarity using certificates on \(o(\log n)\) bits.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10

Similar content being viewed by others

References

  1. Afek, Y., Kutten, S., Yung, M.: The local detection paradigm and its application to self-stabilization. Theor. Comput. Sci. 186(1–2), 199–229 (1997). https://doi.org/10.1016/S0304-3975(96)00286-1

    Article  MathSciNet  MATH  Google Scholar 

  2. Amiri, S.A., de Mendez, P.O., Rabinovich, R., Siebertz, S.: Distributed domination on graph classes of bounded expansion. In: 30th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 143–151 (2018). https://doi.org/10.1145/3210377.3210383

  3. Amiri, S.A., Schmid, S., Siebertz, S.: Distributed dominating set approximations beyond planar graphs. ACM Trans. Algorithms 15(3), 39:1–139:8 (2019). https://doi.org/10.1145/3326170

    Article  MathSciNet  MATH  Google Scholar 

  4. Awerbuch, B.: A new distributed depth-first-search algorithm. Inf. Process. Lett. 20(3), 147–150 (1985). https://doi.org/10.1016/0020-0190(85)90083-3

    Article  MATH  Google Scholar 

  5. Awerbuch, B., Patt-Shamir, B., Varghese, G.: Self-stabilization by local checking and correction (extended abstract). In: 32nd Symposium on Foundations of Computer Science (FOCS), pp. 268–277 (1991). https://doi.org/10.1109/SFCS.1991.185378

  6. Balliu, A., D’Angelo, G., Fraigniaud, P., Olivetti, D.: What can be verified locally? pp. 8:1–8:13 (2017). https://doi.org/10.4230/LIPIcs.STACS.2017.8

  7. Cabello, S.: Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs. ACM Trans. Algorithms 15(2), 21:1–321:8 (2019). https://doi.org/10.1145/3218821

    Article  MathSciNet  MATH  Google Scholar 

  8. Crescenzi, P., Fraigniaud, P., Paz, A.: Trade-offs in distributed interactive proofs. In: 33rd International Symposium on Distributed Computing (DISC), LIPIcs 146, pp. 13:1–13:17. Dagstuhl (2019). https://doi.org/10.4230/LIPIcs.DISC.2019.13

  9. Czygrinow, A., Hańćkowiak, M., Szymanska, E.: Distributed approximation algorithms for planar graphs. In: 6th Italian Conference on Algorithms and Complexity (CIAC), pp. 296–307 (2006). https://doi.org/10.1007/11758471_29

  10. Czygrinow, A., Hańćkowiak, M., Szymanska, E., Wawrzyniak, W., Witkowski, M.: Distributed local approximation of the minimum k-tuple dominating set in planar graphs. In: 18th Int. Conference on Principles of Distributed Systems (OPODIS), pp. 49–59 (2014). https://doi.org/10.1007/978-3-319-14472-6_4

  11. Czygrinow, A., Hańćkowiak, M., Szymanska, E., Wawrzyniak, W., Witkowski, M.: Improved distributed local approximation algorithm for minimum 2-dominating set in planar graphs. Theor. Comput. Sci. 662, 1–8 (2017). https://doi.org/10.1016/j.tcs.2016.12.001

    Article  MathSciNet  MATH  Google Scholar 

  12. Czygrinow, A., Hańćkowiak, M., Wawrzyniak, W.: Distributed packing in planar graphs. In: 20th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 55–61 (2008). https://doi.org/10.1145/1378533.1378541

  13. Czygrinow, A., Hańćkowiak, M., Wawrzyniak, W.: Fast distributed approximations in planar graphs. In: 22nd Int. Symp. on Distributed Computing (DISC), pp. 78–92 (2008). https://doi.org/10.1007/978-3-540-87779-0_6

  14. Diestel, R.: Graph Theory, Graduate Texts in Mathematics, vol. 173. Springer, Berlin (2000)

    Google Scholar 

  15. Esperet, L., Lévêque, B.: Local certification of graphs on surfaces. arXiv preprint arXiv:2102.04133 (2021)

  16. Feuilloley, L.: Introduction to local certification. CoRR abs/1910.12747 (2019). http://arxiv.org/abs/1910.12747

  17. Feuilloley, L.: Bibliography of distributed approximation beyonf bounded degree. CoRR abs/2001.08510 (2020). http://arxiv.org/abs/2001.08510

  18. Feuilloley, L., Fraigniaud, P.: Survey of distributed decision. Bulletin of the EATCS 119 (2016). http://eatcs.org/beatcs/index.php/beatcs/article/view/411

  19. Feuilloley, L., Fraigniaud, P., Hirvonen, J.: A hierarchy of local decision. In: 43rd International Colloquium on Automata, Languages and Programming (ICALP), pp. 118:1–118:15 (2016)

  20. Feuilloley, L., Fraigniaud, P., Hirvonen, J., Paz, A., Perry, M.: Redundancy in distributed proofs. In: 32nd International Symposium on Distributed Computing (DISC), LIPIcs, pp. 24:1–24:18. Dagstuhl (2018). https://doi.org/10.4230/LIPIcs.DISC.2018.24

  21. Feuilloley, L., Fraigniaud, P., Montealegre, P., Rapaport, I., Rémila, É., Todinca, I.: Local certification of graphs with bounded genus. arXiv:2007.08084 (2020)

  22. Feuilloley, L., Hirvonen, J.: Local verification of global proofs. In: 32nd Int. Symp. on Distributed Computing (DISC), LIPIcs 121, pp. 25:1–25:17. Dagstuhl (2018). https://doi.org/10.4230/LIPIcs.DISC.2018.25

  23. Fraigniaud, P., Korman, A., Peleg, D.: Towards a complexity theory for local distributed computing. J. ACM 60(5), 1–26 (2013). https://doi.org/10.1145/2499228

    Article  MathSciNet  MATH  Google Scholar 

  24. Fraigniaud, P., Montealegre, P., Oshman, R., Rapaport, I., Todinca, I.: On distributed Merlin-Arthur decision protocols. In: 26th Int. Colloquium Structural Information and Communication Complexity (SIROCCO), LNCS 11639, pp. 230–245. Springer (2019). https://doi.org/10.1007/978-3-030-24922-9_16

  25. Fraigniaud, P., Patt-Shamir, B., Perry, M.: Randomized proof-labeling schemes. Distrib. Comput. 32(3), 217–234 (2019). https://doi.org/10.1007/s00446-018-0340-8

    Article  MathSciNet  MATH  Google Scholar 

  26. de Fraysseix, H., Rosenstiehl, P.: A characterization of planar graphs by trémaux orders. Combinatorica 5(2), 127–135 (1985). https://doi.org/10.1007/BF02579375

    Article  MathSciNet  MATH  Google Scholar 

  27. Füredi, Z.: An upper bound on Zarankiewicz’problem. Comb. Probab. Comput. 5(1), 29–33 (1996)

    Article  MathSciNet  Google Scholar 

  28. Ghaffari, M., Haeupler, B.: Distributed algorithms for planar networks I: planar embedding. In: ACM Symposium on Principles of Distributed Computing (PODC), pp. 29–38 (2016). https://doi.org/10.1145/2933057.2933109

  29. Ghaffari, M., Haeupler, B.: Distributed algorithms for planar networks II: low-congestion shortcuts, MST, and min-cut. In: 27th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 202–219 (2016). https://doi.org/10.1137/1.9781611974331.ch16

  30. Ghaffari, M., Parter, M.: Near-optimal distributed DFS in planar graphs. In: 31st Int. Symp. on Distributed Computing (DISC), LIPIcs, pp. 21:1–21:16. Dagstuhl (2017). https://doi.org/10.4230/LIPIcs.DISC.2017.21

  31. Göös, M., Suomela, J.: Locally checkable proofs in distributed computing. Theory Comput. 12(1), 1–33 (2016). https://doi.org/10.4086/toc.2016.v012a019

    Article  MathSciNet  MATH  Google Scholar 

  32. Hilke, M., Lenzen, C., Suomela, J.: Brief announcement: local approximability of minimum dominating set on planar graphs. In: ACM Symposium on Principles of Distributed Computing (PODC), pp. 344–346 (2014). https://doi.org/10.1145/2611462.2611504

  33. Hopcroft, J.E., Tarjan, R.E.: Efficient planarity testing. J. ACM 21(4), 549–568 (1974). https://doi.org/10.1145/321850.3218520

    Article  MathSciNet  MATH  Google Scholar 

  34. Itkis, G., Levin, L.A.: Fast and lean self-stabilizing asynchronous protocols. In: 35th Annual Symposium on Foundations of Computer Science (FOCS), pp. 226–239 (1994). https://doi.org/10.1109/SFCS.1994.365691

  35. Kol, G., Oshman, R., Saxena, R.R.: Interactive distributed proofs. In: ACM Symposium on Principles of Distributed Computing (PODC), pp. 255–264 (2018). https://doi.org/10.1016/S0304-3975(96)00286-11

  36. Korman, A., Kutten, S., Peleg, D.: Proof labeling schemes. Distrib, Comput. 22(4), 215–233 (2010). https://doi.org/10.1007/s00446-010-0095-3

    Article  MATH  Google Scholar 

  37. Kuhn, F., Moscibroda, T., Wattenhofer, R.: What cannot be computed locally! In: 23rd ACM Symposium on Principles of Distributed Computing (PODC), pp. 300–309 (2004). https://doi.org/10.1145/1011767.1011811

  38. Lenzen, C., Oswald, Y.A., Wattenhofer, R.: What can be approximated locally?: case study: dominating sets in planar graphs. In: 20th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 46–54 (2008). https://doi.org/10.1145/1378533.1378540

  39. Lenzen, C., Pignolet, Y.A., Wattenhofer, R.: Distributed minimum dominating set approximations in restricted families of graphs. Distrib. Comput. 26(2), 119–137 (2013). https://doi.org/10.1007/s00446-013-0186-z

    Article  MATH  Google Scholar 

  40. Naor, M., Parter, M., Yogev, E.: The power of distributed verifiers in interactive proofs. In: 31st ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1096–115 (2020). https://doi.org/10.1137/1.9781611975994.67

  41. Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. SIAM, Philadelphia (2000)

    Book  Google Scholar 

  42. Peleg, D., Rubinovich, V.: A near-tight lower bound on the time complexity of distributed minimum-weight spanning tree construction. SIAM J. Comput. 30(5), 1427–1442 (2000). https://doi.org/10.1137/S00975397003697404

    Article  MathSciNet  MATH  Google Scholar 

  43. Roditty, L., Williams, V.V.: Fast approximation algorithms for the diameter and radius of sparse graphs. In: 45th ACM Symposium on Theory of Computing (STOC), pp. 515–524 (2013). https://doi.org/10.1145/2488608.2488673

  44. Sarma, A.D., Holzer, S., Kor, L., Korman, A., Nanongkai, D., Pandurangan, G., Peleg, D., Wattenhofer, R.: Distributed verification and hardness of distributed approximation. SIAM J. Comput. 41(5), 1235–1265 (2012). https://doi.org/10.1016/S0304-3975(96)00286-15

    Article  MathSciNet  MATH  Google Scholar 

  45. Wawrzyniak, W.: A strengthened analysis of a local algorithm for the minimum dominating set problem in planar graphs. Inf. Process. Lett. 114(3), 94–98 (2014). https://doi.org/10.1016/j.ipl.2013.11.0086

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

Additional support from MIPP and José Correa’s Amazon Research Award (L.F.). Additional support from ANR project DESCARTES, and from INRIA project GANG (P.F.). Additional support from CONICYT via PAI + Convocatoria Nacional Subvención a la Incorporación en la Academia Año 2017 + PAI77170068 and FONDECYT 11190482 (P.M.). Additional support from CONICYT via PIA/Apoyo a Centros Científicos y Tecnológicos de Excelencia AFB 170001 and Fondecyt 1170021 (I.R.). Additional support from IDEXLYON (project INDEPTH) within the Programme Investissements d’Avenir (ANR-16-IDEX-0005) and “Mathématiques de la Décision pour l’Ingénierie Physique et Sociale” (MODMAD).

Author information

Authors and Affiliations

  1. Facultad de Ingeniería y Ciencias, Universidad Adolfo Ibañez, Santiago, Chile

    Pedro Montealegre

  2. LIRIS UMR CNRS 5205, University of Lyon, Université Lyon 1, Lyon, 69621, France

    Laurent Feuilloley

  3. IRIF, CNRS, Université de Paris, Paris , France

    Pierre Fraigniaud

  4. DIM-CMM (UMI 2807 CNRS), Universidad de Chile, Santiago, Chile

    Ivan Rapaport

  5. GATE Lyon St-Etienne (UMR 5824 CNRS), UJM, St-Étienne, France

    Éric Rémila

  6. LIFO, Université d’Orléans, INSA Centre-Val de Loire, Orléans, France

    Ioan Todinca

Authors
  1. Laurent Feuilloley
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Pierre Fraigniaud
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Pedro Montealegre
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Ivan Rapaport
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Éric Rémila
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Ioan Todinca
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Pedro Montealegre.

Ethics declarations

Conflict of interest

The authors declare that they have no conflict of interest.

Additional information

A preliminary version of this paper appeared in the proceedings of the 39th ACM Symposium on Principles of Distributed Computing (PODC), 3–7 August 2020, Salerno, Italy.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Feuilloley, L., Fraigniaud, P., Montealegre, P. et al. Compact Distributed Certification of Planar Graphs. Algorithmica 83, 2215–2244 (2021). https://doi.org/10.1007/s00453-021-00823-w

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-021-00823-w

Keywords

Search

Navigation