Move Complexity of a Self-Stabilizing Algorithm for Maximal Independent Sets

Abstract

${\mathcal{A}}_{\mathsf{deg}}$ is a self-stabilizing algorithm that computes a maximal independent set in a finite graph with approximation ratio $(\Delta +2)/3$. In this note we show that under the central scheduler the number of moves of ${\mathcal{A}}_{\mathsf{deg}}$ is not bounded by a polynomial in $n$.