Minimal controllability problems

Alex Olshevsky

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Article number6851897
Pages (from-to)249-258
Number of pages10
JournalIEEE Transactions on Control of Network Systems
Issue number3
StatePublished - Sep 1 2014


  • Controllability
  • control design
  • linear feedback control systems

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Signal Processing
  • Computer Networks and Communications
  • Control and Optimization


Dive into the research topics of 'Minimal controllability problems'. Together they form a unique fingerprint.

Cite this