I'm looking to figure out whether there are any general results about or examples concerning the NP-completeness of the problem of finding a second solution to an NP-complete problem. More precisely, I'm interested in any problems of the following form:
Given a solution $S$ to an instance $I$ of an NP-complete problem, is there a solution $S' \neq S$ to $I$?
Any examples of problems of this sort, both NP-complete and not, or general work, or even a what this sort of problem is called (so I can properly do my own searching) would be appreciated.
Another question addresses this issue specifically as pertaining to SAT.
I hope I'm not asking something really basic; there don't seem to be any examples in Garey and Johnson of this kind of thing.
Thanks
Mark C.