TY - GEN
T1 - Compact Distributed Interactive Proofs for the Recognition of Cographs and Distance-Hereditary Graphs
AU - Montealegre, Pedro
AU - Ramírez-Romero, Diego
AU - Rapaport, Ivan
N1 - Publisher Copyright:
© 2021, Springer Nature Switzerland AG.
PY - 2021
Y1 - 2021
N2 - We present compact distributed interactive proofs for the recognition of two important graph classes, well-studied in the context of centralized algorithms, namely complement reducible graphs and distance-hereditary graphs. Complement reducible graphs (also called cographs) are defined as the graphs not containing a four-node path P4 as an induced subgraph. Distance-hereditary graphs are a super-class of cographs, defined as the graphs where the distance (shortest paths) between any pair of vertices is the same on every induced connected subgraph. First, we show that there exists a distributed interactive proof for the recognition of cographs with two rounds of interaction. More precisely, we give a dAM protocol with a proof size of O(log n) bits that recognizes cographs with high probability. Moreover, our protocol can be adapted to verify any Turing-decidable predicate restricted to cographs in dAM with certificates of size O(log n). Second, we give a three-round, dMAM interactive protocol for the recognition of distance-hereditary graphs, still with a proof size of O(log n) bits. Finally, we show that any one-round (denoted dM ) or two-round, dMA protocol for the recognition of cographs or distance-hereditary graphs requires certificates of size Ω(log n) bits. Moreover, we show that any constant-round dAM protocol using shared randomness requires certificates of size Ω(log log n).
AB - We present compact distributed interactive proofs for the recognition of two important graph classes, well-studied in the context of centralized algorithms, namely complement reducible graphs and distance-hereditary graphs. Complement reducible graphs (also called cographs) are defined as the graphs not containing a four-node path P4 as an induced subgraph. Distance-hereditary graphs are a super-class of cographs, defined as the graphs where the distance (shortest paths) between any pair of vertices is the same on every induced connected subgraph. First, we show that there exists a distributed interactive proof for the recognition of cographs with two rounds of interaction. More precisely, we give a dAM protocol with a proof size of O(log n) bits that recognizes cographs with high probability. Moreover, our protocol can be adapted to verify any Turing-decidable predicate restricted to cographs in dAM with certificates of size O(log n). Second, we give a three-round, dMAM interactive protocol for the recognition of distance-hereditary graphs, still with a proof size of O(log n) bits. Finally, we show that any one-round (denoted dM ) or two-round, dMA protocol for the recognition of cographs or distance-hereditary graphs requires certificates of size Ω(log n) bits. Moreover, we show that any constant-round dAM protocol using shared randomness requires certificates of size Ω(log log n).
KW - Cographs
KW - Distance hereditary graph
KW - Distributed interactive proofs
KW - Distributed recognition of graph classes
UR - http://www.scopus.com/inward/record.url?scp=85119833555&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-91081-5_26
DO - 10.1007/978-3-030-91081-5_26
M3 - Conference contribution
AN - SCOPUS:85119833555
SN - 9783030910808
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 395
EP - 409
BT - Stabilization, Safety, and Security of Distributed Systems - 23rd International Symposium, SSS 2021, Proceedings
A2 - Johnen, Colette
A2 - Schiller, Elad Michael
A2 - Schmid, Stefan
PB - Springer Science and Business Media Deutschland GmbH
T2 - 23rd International Symposium on Stabilization, Safety, and Security of Distributed Systems, SSS 2021
Y2 - 17 November 2021 through 20 November 2021
ER -