Distributed Interactive Proofs for the Recognition of Some Geometric Intersection Graph Classes

Benjamin Jauregui, Pedro Montealegre, Ivan Rapaport

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

Abstract

A graph G= (V, E) is a geometric intersection graph if every node v∈ V is identified with a geometric object of some particular type, and two nodes are adjacent if the corresponding objects intersect. Geometric intersection graph classes have been studied from both the theoretical and practical point of view. On the one hand, many hard problems can be efficiently solved or approximated when the input graph is restricted to a geometric intersection class of graphs. On the other hand, these graphs appear naturally in many applications such as sensor networks, scheduling problems, and others. Recently, in the context of distributed certification and distributed interactive proofs, the recognition of graph classes has started to be intensively studied. Different results related to the recognition of trees, bipartite graphs, bounded diameter graphs, triangle-free graphs, planar graphs, bounded genus graphs, H-minor free graphs, etc., have been obtained. The goal of the present work is to design efficient distributed protocols for the recognition of relevant geometric intersection graph classes, namely permutation graphs, trapezoid graphs, circle graphs and polygon-circle graphs. More precisely, for the two first classes we give proof labeling schemes recognizing them with logarithmic-sized certificates. For the other two classes, we give three-round distributed interactive protocols that use messages and certificates of size O(log n). Finally, we provide logarithmic lower-bounds on the size of the certificates on the proof labeling schemes for the recognition of any of the aforementioned geometric intersection graph classes.

Original languageEnglish
Title of host publicationStructural Information and Communication Complexity - 29th International Colloquium, SIROCCO 2022, Proceedings
EditorsMerav Parter
PublisherSpringer Science and Business Media Deutschland GmbH
Pages212-233
Number of pages22
ISBN (Print)9783031099922
DOIs
StatePublished - 2022
Externally publishedYes
Event29th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2022 - Paderborn, Germany
Duration: 27 Jun 202229 Jun 2022

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13298 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference29th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2022
Country/TerritoryGermany
CityPaderborn
Period27/06/2229/06/22

Keywords

  • Distributed decision
  • Distributed interactive proofs
  • Intersection Graph Classes
  • Proof-labeling scheme

Fingerprint

Dive into the research topics of 'Distributed Interactive Proofs for the Recognition of Some Geometric Intersection Graph Classes'. Together they form a unique fingerprint.

Cite this