The complexity of completing partial Latin squares

Research output: Contribution to journalArticlepeer-review

121 Scopus citations


Completing partial Latin squares is shown to be NP-complete. Classical embedding techniques of Hall and Ryser underly a reduction from partitioning tripartite graphs into triangles. This in turn is shown to be NP-complete using a recent result of Holyer.

Original languageEnglish (US)
Pages (from-to)25-30
Number of pages6
JournalDiscrete Applied Mathematics
Issue number1
StatePublished - Apr 1984
Externally publishedYes

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics


Dive into the research topics of 'The complexity of completing partial Latin squares'. Together they form a unique fingerprint.

Cite this