What is known about the complexity of creating Block Designs (https://en.wikipedia.org/wiki/Block_design)?

I've found one paper that creates approximately solutions using Metaheuristics that claims that Block Design is NP-Hard, citing a paper from 1978. But that paper from 1978 makes no such claim or proof.

I'm particularly interested in the special case of Projective planes (https://en.wikipedia.org/wiki/Block_design#Projective_planes).

  • $\begingroup$ Complexity given what input? Just the number of vertices? All the parameters of the design? $\endgroup$ Oct 18 '19 at 17:22
  • $\begingroup$ Given any of the above. Happy with either complexity of specific classes or more general results. In particular, any classes that are know to be NP-hard as claimed by previous papers. $\endgroup$
    – Wayne
    Apr 30 '20 at 5:44
  • $\begingroup$ It would help if you could include a link to the paper "that creates approximately solutions using metaheuristics". Perhaps they meant to refer to a different paper? But it is hard to tell without seeing it. $\endgroup$ Apr 30 '20 at 16:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.