Is there a list of known problems? Is there a database of known problems with information about their complexity and algorithms, related problems, references etc that is available to us?  [If not, can we make one? I know this is off topic, but it would be SO useful]
If you do not insist on a database, the Encyclopedia of algorithms By Ming-Yang Kao is very valuable reference. The above link is the entry for the minimum Bandwidth problem.


  This is an encyclopedia of algorithms that sets out the solutions to important algorithmic problems. It aims to be a comprehensive collection and is designed to provide quick and easy access for both students and researchers.” (Kybernetes, Vol. 38 (1/2), 2009)