## Abstract

We present a complete classification of the deterministic distributed time complexity for a family of graph problems: binary labeling problems in trees in the usual LOCAL model of distributed computing. These are locally checkable problems that can be encoded with an alphabet of size two in the edge labeling formalism. Examples of binary labeling problems include sinkless orientation, sinkless and sourceless orientation, 2-vertex coloring, and perfect matching. We show that the complexity of any such problem is in one of the following classes: O(1), Θ(log n), Θ(n), or unsolvable. Furthermore, given the description of any binary labeling problem, we can easily determine in which of the four classes it is and what is an asymptotically optimal algorithm for solving it.

Original language | English |
---|---|

Title of host publication | PODC 2020 - Proceedings of the 39th Symposium on Principles of Distributed Computing |

Publisher | ACM |

Pages | 349-351 |

Number of pages | 3 |

ISBN (Electronic) | 9781450375825 |

DOIs | |

Publication status | Published - 31 Jul 2020 |

MoE publication type | A4 Article in a conference publication |

Event | ACM Symposium on Principles of Distributed Computing - Virtual, Online, Italy Duration: 3 Aug 2020 → 7 Aug 2020 Conference number: 39 |

### Conference

Conference | ACM Symposium on Principles of Distributed Computing |
---|---|

Abbreviated title | PODC |

Country | Italy |

City | Virtual, Online |

Period | 03/08/2020 → 07/08/2020 |

## Keywords

- distributed computational complexity
- graph problems
- LOCAL model
- locally checkable labeling problems