Input-output decomposition of dynamic systems is NP-complete
Robert Endre Tarjan · IEEE Transactions on Automatic Control · 1984
Pichai, Sezar, and Siljak have studied a decomposition technique for acyclic graphs, called input-output decomposition, that simplifies the analysis of dynamic systems. We show that the problem of determining whether a given graph is decomposable is NP-complete. Since this makes the existence of a polynomial-time decomposition algorithm unlikely, the possible benefits of having an input-output decomposition may be outweighed by the difficulty of finding one.