  We study the problem of optimal leader selection in consensus networks under
two performance measures (1) formation coherence when subject to additive
perturbations, as quantified by the steady-state variance of the deviation from
the desired trajectory, and (2) convergence rate to a consensus value. The
objective is to identify the set of $k$ leaders that optimizes the chosen
performance measure. In both cases, an optimal leader set can be found by an
exhaustive search over all possible leader sets; however, this approach is not
scalable to large networks. In recent years, several works have proposed
approximation algorithms to the $k$-leader selection problem, yet the question
of whether there exists an efficient, non-combinatorial method to identify the
optimal leader set remains open. This work takes a first step towards answering
this question. We show that, in one-dimensional weighted graphs, namely path
graphs and ring graphs, the $k$-leader selection problem can be solved in
polynomial time (in both $k$ and the network size $n$). We give an $O(n^3)$
solution for optimal $k$-leader selection in path graphs and an $O(kn^3)$
solution for optimal $k$-leader selection in ring graphs.

Optimization and Control;Systems and Control