Can I read Recognizing Hereditary Properties in the Presence of Byzantine Nodes on EtoBox?

Recognizing Hereditary Properties in the Presence of Byzantine Nodes by Cifuentes-Núñez, David; Montealegre, Pedro; Rapaport, Ivan is a scholarly article available to read on EtoBox.

What is Recognizing Hereditary Properties in the Presence of Byzantine Nodes about?

Augustine et al. [DISC 2022] initiated the study of distributed graph algorithms in the presence of Byzantine nodes in the congested clique model. In this model, there is a set $B$ of Byzantine nodes, where $|B|$ is less than a third of the total number of nodes. These nodes have complete knowledge of the network and the state of other nodes, and they conspire to alter the output of the system. The authors addressed the connectivity problem, showing that it is solvable under the promise that either the subgraph induced by the honest nodes is connected, or the graph has $2|B|+1$ connected components. In the current work, we continue the study of the Byzantine congested clique model by considering the recognition of other graph properties, specifically \emph{hereditary properties}. A graph property is \emph{hereditary} if it is closed under taking induced subgraphs. Examples of hereditary properties include acyclicity, bipartiteness, planarity, and bounded (chromatic, independence) number, etc. For each class of graphs $\mathcal{G}$ satisfying an hereditary property (an hereditary graph-class), we propose a randomized algorithm which, with high probability, (1) accepts if the input g

Author

Cifuentes-Núñez, David; Montealegre, Pedro; Rapaport, Ivan

Published

2023

Language

EN