Some Complexity Problems on Single Input Double Output Controllers

Abstract

We investigate the time complexity of constructing single input
double output state feedback controller structures, given the
directed structure graph G of a system. Such a controller structure
defines a restricted type of P3-partition of the graph G. A necessary
condition (*) has been found and two classes of graphs have
been identified where the search problem of finding a feasible P3-
partition is polynomially solvable and, in addition, (*) is not only
necessary but also sufficient for the existence of a P3-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, a stabilizing
structure with Single Input m-Output controllers can be found in
polynomial time for the system in question, if it admits one.