Pichai, Sezar, and Å iljak 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.
All Science Journal Classification (ASJC) codes
- Control and Systems Engineering
- Computer Science Applications
- Electrical and Electronic Engineering