We investigate the time complexity of constructing single input
double output state feedback controller structures, given the directed
structure graph
![$G$](Abs/img1.gif)
of a system. Such a controller structure defines a
restricted type of
![$P_3$](Abs/img2.gif)
-partition of the graph
![$G$](Abs/img1.gif)
. A necessary condition
![$(*)$](Abs/img3.gif)
has been found and two classes of graphs have been identified where the
search problem of finding a feasible
![$P_3$](Abs/img2.gif)
-partition is polynomially solvable
and, in addition,
![$(*)$](Abs/img3.gif)
is not only necessary but also sufficient for the
existence of a
![$P_3$](Abs/img2.gif)
-partition. It is shown further that the decision problem
on two particular graph classes -- defined in terms of forbidden subgraphs
-- remains
NP-complete, but is polynomially solvable on the
intersection of those two classes. Moreover, for every natural number
![$m$](Abs/img4.gif)
, a
stabilizing structure with Single Input
![$m$](Abs/img4.gif)
-Output controllers can be found
in polynomial time for the system in question, if it admits one