Yes, but in practice heuristic approaches can work well, even if there are no guarantees of optimality. See for example my response about a simple "most constrained first" heuristic.