The computational complexity of decomposing block designs

Charles J. Colbourn, Marlene J. Colbourn

Research output: Contribution to journalArticlepeer-review


Deciding whether a (balanced incomplete) block design with λ = 3 can be decomposed, or partitioned, into block designs with smaller λ is shown to be NP-complete. The transformation employs known NP-completeness results on edge-partitioning graphs into triangles. The reduction also furnishes a construction of indecomposable triple systems with arbitrary odd λ, settling a question of Kramer.

Original languageEnglish (US)
Pages (from-to)345-350
Number of pages6
JournalNorth-Holland Mathematics Studies
Issue numberC
StatePublished - Jan 1 1985
Externally publishedYes

ASJC Scopus subject areas

  • General Mathematics


Dive into the research topics of 'The computational complexity of decomposing block designs'. Together they form a unique fingerprint.

Cite this