  This paper investigates two related optimal input selection problems for
fixed (non-switched) and switched structured systems. More precisely, we
consider selecting the minimum cost of inputs from a prior set of inputs, and
selecting the inputs of the smallest possible cost with a bound on their
cardinality, all to ensure system structural controllability. Those problems
have attracted much attention recently; unfortunately, they are NP-hard in
general. In this paper, it is found that, if the input structure satisfies
certain `regularizations', which are characterized by the proposed restricted
total unimodulairty notion, those problems can be solvable in polynomial time
via linear programming (LP) relaxations. Particularly, the obtained
characterizations depend only on the incidence matrix relating the inputs and
the source strongly connected components (SCC) of the system structure,
irrespective of how the inputs actuate states within the same SCC. They cover
all the currently known polynomially solvable cases (such as the dedicated
input case), and contain many new cases unexploited in the past, among which
the source-SCC separated input (SSSI) constraint is highlighted. Further, for
switched systems, the obtained polynomially solvable condition (namely the
joint SSSI constraint) does not require each of the subsystems to satisfy the
SSSI constraint. We achieve these by first formulating those problems as
equivalent integer linear programmings (ILPs), and then proving total
unimodularity of the corresponding constraint matrices. This property allows us
to solve those ILPs efficiently via LP-relaxation. We also discuss solutions
obtained via LP-relaxation and LP-rounding in the general case. Several
examples are given to illustrate the obtained theoretical results.
