The Taub Faculty of Computer Science Events and Talks

In this work, we study the complexity of computing the distance of a graph from being triangle-free in distributed settings, that is, computing the minimum number of edges that must be removed to achieve a graph without triangles. We present lower bounds for the exact solution showing that this task is “as hard as it gets”. We also show fast algorithms for approximate solutions in multiple distributed models.