Complexity of finding a second solution given a correct solution to an NP-complete problem 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.
The question seems to be solved while I was writing this answer, but let me post my answer anyway.

Yato and Seta [YS03] (both are my colleagues when I was a student) propose a general framework to prove the NP-completeness of this kind of problems, where they are called Another Solution Problems or ASPs, and prove the NP-completeness of the ASPs of many puzzles.  They consider a restricted notion of reductions between relation problems called ASP reductions, and show that the NP-hardness of ASPs is preserved under ASP reductions and show that many known reductions can be in fact viewed as or modified to ASP reductions between natural relation problems.

[YS03] Takayuki Yato and Takahiro Seta.  Complexity and completeness of finding another solution and its application to puzzles.  IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E86-A(5):1052–1060, May 2003.