  In this paper, we address two minimal controllability problems, where the
goal is to determine a minimal subset of state variables in a linear
time-invariant system to be actuated to ensure controllability under additional
constraints. First, we study the problem of characterizing the sparsest input
matrices that assure controllability when the autonomous dynamics' matrix is
simple. Secondly, we build upon these results to describe the solutions to the
robust minimal controllability problem, where the goal is to determine the
sparsest input matrix ensuring controllability when specified number of inputs
fail. Both problems are NP-hard, but under the assumption that the dynamics'
matrix is simple, we show that it is possible to reduce these two problems to
set multi-covering problems. Consequently, these problems share the same
computational complexity, i.e., they are NP-complete, but polynomial algorithms
to approximate the solutions of a set multi-covering problem can be leveraged
to obtain close-to-optimal solutions to either of the minimal controllability
problems.
