Relation between leader-follower consensus control and feedback vertex sets

Leader-follower consensus control is a kind of consensus control, where some special agents, called the leaders, have relatively high flexibility in changing their states, and the other agents, called the followers, follow the leaders. One of the important issues for leader-follower consensus control is a leader selection problem, i.e. determining leaders to achieve a desired performance. On the other hand, the notion of a feedback vertex set is well-known in graph theory. Feedback vertex sets are known to play an important role in various problems, e.g. deadlock avoidance and sensing node selection of biological networks. Thus, they are expected to be closely related to leader-follower consensus control. However, their relationship has never been studied so far. This paper discloses the relationship between leader selection and feedback vertex sets. We deal with a problem of finding a minimum leader set to achieve the fastest convergence to consensus and show that a solution to the leader selection problem is given by a feedback vertex set.