Efficient, optimal k-leader selection for coherent, one-dimensional formations

We study the problem of optimal leader selection in consensus networks with noisy relative information. The objective is to identify the set of k leaders that minimizes the formation´s deviation from the desired trajectory established by the leaders. 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³) solution for optimal k-leader selection in path graphs and an O(kn³) solution for optimal k-leader selection in ring graphs.