Tight Lower Bounds in the Supported LOCAL Model
Alkida Balliu, Thomas Boudier, Sebastian Brandt, Dennis Olivetti · 2024
In this work, we study the complexity of fundamental distributed graph problems in the recently popular setting where information about the input graph is available to the nodes before the start of the computation. We focus on the most common such setting, known as the Supported LOCAL model, where the input graph---on which the studied graph problem has to be solved---is guaranteed to be a subgraph of the underlying communication network.