Some Complexity Problems on Single Input Double Output Controllers

Katalin M. Hangos
Zsolt Tuza
Anders Yeo



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 $P_3$-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 $P_3$-partition is polynomially solvable and, in addition, $(*)$ is not only necessary but also sufficient for the existence of a $P_3$-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

Available as PostScript, PDF.


Last modified: 2003-06-08 by webmaster.