Some complexity problems on single input double output controllers

We investigate the time complexity of constructing single input double output state feedback controller structures, given the directed structure graph GG of a system. Such a controller structure defines a restricted type of P3P3-partition of the graph GG. A necessary condition (∗) is described and some classes of graphs are identified where the search problem of finding a feasible P3P3-partition is polynomially solvable and, in addition, (∗) is not only necessary but also sufficient for the existence of a P3P3-partition. It is also proved 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. The polynomial-time solvability of some further related problems is shown, too.