Title: Determining r-Robustness of Arbitrary Digraphs Using Zero-One Linear Integer Programming,
Abstract: There has been an increase in the use of resilient control algorithms based
on the graph theoretic properties of $r$- and $(r,s)$-robustness. These
algorithms guarantee consensus of normally behaving agents in the presence of a
bounded number of arbitrarily misbehaving agents if the values of the integers
$r$ and $s$ are sufficiently high. However, determining the largest integer $r$
for which an arbitrary digraph is $r$-robust is highly nontrivial. This paper
introduces a novel method for calculating this value using zero-one integer
programming. The method only requires knowledge of the graph Laplacian matrix,
and can be formulated with affine objective and constraints, except for the
integer constraint. Integer programming methods such as branch-and-bound can
allow both lower and upper bounds on $r$ to be iteratively tightened.
Simulations suggest the proposed method demonstrates greater efficiency than
prior algorithms.