Input-Output Decomposition of Dynamic Systems is NP-Complete

Research output: Contribution to journalArticlepeer-review

5 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)863-864
Number of pages2
JournalIEEE Transactions on Automatic Control
Issue number9
StatePublished - 1984
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Control and Systems Engineering
  • Computer Science Applications
  • Electrical and Electronic Engineering


Dive into the research topics of 'Input-Output Decomposition of Dynamic Systems is NP-Complete'. Together they form a unique fingerprint.

Cite this