  This paper considers the problem of minimal control inputs to affect the
system states such that the resulting system is structurally controllable. This
problem and the dual problem of minimal observability are claimed to have no
polynomial-order exact solution and, therefore, are NP-hard. Here, adopting a
graph-theoretic approach, this problem is solved for general nonlinear (and
also structure-invariant) systems and a P-order solution is proposed. In this
direction, the dynamical system is modeled as a directed graph, called
\textit{system digraph}, and two types of graph components are introduced which
are tightly related with structural controllability. Two types of nodes which
are required to be affected (or driven) by an input, called \textit{driver
nodes}, are defined, and minimal number of these driver nodes are obtained.
Polynomial-order complexity of the given algorithms to solve the problem
ensures applicability of the solution for analysis of large-scale dynamical
systems. {The structural results in this paper are significant as compared to
the existing literature which offer approximate and computationally
less-efficient, e.g. Gramian-based, solutions for the problem, while this paper
provides exact solution with lower computational complexity and applicable for
controllability analysis of nonlinear systems.
