21
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ Mark, if cstheory.stackexchange.com/questions/1639/… answers your question, do let me know, and we can mark this as a duplicate. I'm asking because your question seems quite open ended, and maybe the answers there might help $\endgroup$
    – Suresh Venkat
    Dec 5, 2010 at 23:31
  • $\begingroup$ Ah, yes, it does seem to answer it. Clearly, "Another Solution Problem" is what I was looking for. Thank you! $\endgroup$
    – Mark C.
    Dec 5, 2010 at 23:36
  • 1
    $\begingroup$ Tsuyoshi's answer seems quite distinct from the other ones, so I'm not sure it makes sense to close this question. Maybe Mark, you could add a note to the question forwarding readers to the other question (which is specific to SAT) ? $\endgroup$
    – Suresh Venkat
    Dec 5, 2010 at 23:50

4 Answers 4

Reset to default
17
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ I know someone who is considering this as a possible direction for a PhD thesis, and we talked about it briefly, though I know nothing about the area. It doesn't seem as though there's been much followup since the paper you cite, though perhaps my search skills are weak. Are you aware of any significant papers since 2003? $\endgroup$
    – Aaron Sterling
    Dec 6, 2010 at 0:01
  • 3
    $\begingroup$ @Aaron: There are other problems shown to be FNP-complete under ASP reducibility. Also, there are several papers on this subject by Takayuki and others (including one paper where I am a coauthor :) ), and Takayuki wrote a PhD thesis on this topic. One of the later improvements is a formulation based on promise problems, which becomes essential particularly when we deal with PSPACE-completeness and EXP-completeness of ASPs. Unfortunately, none of the papers seems to be freely available (I feel stupid, but even I cannot access my own paper behind the paywall). You may want to contact him. $\endgroup$
    – Tsuyoshi Ito
    Dec 6, 2010 at 0:25
  • 4
    $\begingroup$ +1 for a great answer, and for "even I cannot access my own paper behind the paywall", hehe $\endgroup$
    – Daniel Apon
    Dec 6, 2010 at 5:23
9
$\begingroup$

Laurent Juban in Dichotomy Theorem for the Generalized Unique Satisability Problem proved a dichotomy theorem for Another SAT defined as:

Input: a propositional formula $\phi$ and a satisfying assignment (model) $m$ of $\phi$

Question: Is there another satisfying assignment of $\phi$ different from $m$?

Here an excerpt from the paper with the dichotomy theorem:

Theorem 1 (Dichotomy Theorem). Let $S$ be a finite set of logical relations. If $S$ satisfies one of the conditions (1) to (6) below, then ANOTHER SAT(S) and UNIQUE SAT(S) are polynomial-time solvable. Otherwise, ANOTHER SAT(S) is $NP$-complete and UNIQUE SAT(S) is $coNP$-hard.

  1. Every satisfiable relation in $S$ is 0-valid and 1-valid.
  1. Every relation in $S$ is complementive.
  1. Every relation in $S$ is Horn.
  1. Every relation in $S$ is anti-Horn.
  1. Every relation in $S$ is affine.
  1. Every relation in $S$ is 2SAT.
Improve this answer
$\endgroup$
2
  • $\begingroup$ Yet another variant of Shaefer’s theorem which is false as stated. Let $S=\{\bot,x\lor y\lor\neg z,x\lor\neg y\lor\neg z\}$. Then $S$ violates all six conditions, but both problems are poly-time for $S$: if an $S$-formula contains $\bot$, it is not satisfiable at all. Otherwise, it is in fact an $S'$-formula, where $S'=S\setminus\{\bot\}$ obeys condition 1, hence it has at least two explicitly given satisfying assignments. $\endgroup$
    – Emil Jeřábek
    Nov 2, 2012 at 17:00
  • $\begingroup$ That is, in order for the theorem to hold, condition 1 must be corrected to “every satisfiable relation in $S$ is 0-valid and 1-valid”. $\endgroup$
    – Emil Jeřábek
    Nov 2, 2012 at 17:08
8
$\begingroup$

Given a Hamilton circuit in a graph find another hamilton circuit. This is FNP-complete. Interestingly, there are problems in which the "another solution" is guaranteed to exist by a parity argument. For example : Given a Hamilton circuit in a 3-regular graph, find a second Hamilton circuit. Note that finding a hamiltonian circuit in 3-regular graph is NP-complete. Finding the second one, given that the graph is hamiltonian, is in PPA.

See my blog post for more details.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ NAE-SAT as well. it always has an even number of solutions. $\endgroup$
    – Suresh Venkat
    Dec 6, 2010 at 4:23
  • $\begingroup$ According to the above dichotomy, Another NAE-SAT is polynomially solvable (as stated in the paper). $\endgroup$
    – Mohammad Al-Turkistany
    Dec 6, 2010 at 5:37
  • $\begingroup$ Sure. but it's a lot easier for NAE-SAT: take the given assignment and flip it. linear time ! :) $\endgroup$
    – Suresh Venkat
    Dec 6, 2010 at 7:08
1
$\begingroup$

Here is another example from this paper THE COMPUTATIONAL COMPLEXITY OF RECOGNIZING CRITICAL SETS:

Unique edge-partitioning into triangles is $NP$-complete

Input: Tripartite graph $G$ and an edge partition into triangles

Question: Is there another edge-partition different from the given one?

The paper also proves that $NP$-completeness of this problem

Input: Partial Latin square $P$ with a given a Latin square completing $P$

Question: Is there another completion to a Latin square?

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.