Minimal Controllability Problems

By Alexander Olshevsky. IEEE Transactions on Control of Network Systems, 2013

337 citations recorded by the source corpus.

Given a linear system, we consider the problem of finding a small set of variables to affect with an input so that the resulting system is controllable. We show that this problem is NP-hard; indeed, we show that even approximating the minimum number of variables that need to be affected within a multiplicative factor of clog n is NP-hard for some positive c. On the positive side, we show it is possible to find sets of variables matching this in approximability barrier in polynomial time. This can be done with a simple greedy heuristic which sequentially picks variables to maximize the rank increase of the controllability matrix. Experiments on Erdos-Renyi random graphs that demonstrate this heuristic almost always succeed at finding the minimum number of variables.

Subfields: Artificial Intelligence, Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/31cb7e44270bb691a818ed3ed82f3d0d5a233642

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

Citations in the corpus

On Submodularity and Controllability in Complex Dynamical Networks (2014, background): “Note that Olshevsky has analyzed a greedy algorithm for maximizing the rank of the controllability matrix, though not in a submodularity framework [33].”
Control Principles of Complex Networks (2015, background): “We can prove that finding a control strategy leading to the desired final state is NP-hard for a general Boolean network and this problem can be solved in polynomial time only if the network has a tree structure or contains at most one directed cycle (Akutsu et al., 2007).”