IIRC without that restriction the problem is "just" NP-complete.