When proving NP-completeness do I only need one instance of a problem or all of them?

Question

I saw a proof of reduction of hamiltonian path to spanning tree with inner vertices having degree of k.

The person, who proved it, constructed a spanning tree from a hamiltonian path, basically u-x1-...-xi-...-xn-v, and where xi are inner vertices and then appended k-2 leaves to each one of those vertices.

I understand that that is indeed a correct spanning tree for the problem, and the u-v path does form a hamiltonian path.

But my question is, is this reduced algorithm supposed to find all such spanning trees or not?

I can create a spanning tree with inner vertices of degree k, in which there's no such hamiltonian path that spans all inner vertices, for example, and clearly this method won't work. So this makes the shown construction isolated, meaning it doesn't describe a general case of a spanning tree.

So is it enough to to just construct a certain instance of the problem B we want to prove to be NP-complete, or do we need to reduce a known problem A to the general case of B?

I am confused about this, because, for example, we can prove INDEPENDENT-SET to be NP-complete by reducing CLIQUE to it, and it involves just taking the inverse of the graph and then finding a clique in it. This case does reduce problem CLIQUE to the general case of INDEPENDENT-SET.

P.S. I am very new to NP-completeness.

Answer 1

When you reduce Hamiltonian-Path (HP) to Spanning-Tree-with-inner-degree-$k$ (ST), you show that if you could solve ST then you could solve HP, and moreover in a specific way. If the resulting tree is not completely general, say it is always a Hamiltonian path with attached leaves, then you are actually proving the stronger result that the corresponding promise problem is already NP-hard.

A promise problem is one in which it is guaranteed that the input is either a Yes instance or a No instance, and the task is to distinguish only those two cases. In your case, the promise version is defined in this way:

• Yes instance: the graph contains a spanning tree formed by a Hamiltonian path backbone and $k-2$ leaves attached to all internal vertices;
• No instance: the graph contains no spanning tree in which the degrees of all internal vertices are $k$.

If a graph falls into neither class, we don't care what the answer is. Your proof shows that it is NP-hard to distinguish the Yes instances from the No instances.

We usually don't formulate NP-hardness results this way since it is more cumbersome, but you're right that the proof shows something more. However, if you only cared about the NP-hardness of ST, then there is no need for the reduction to potentially produce all Yes instances of ST. This is because the proof that the reduction implies NP-hardness of ST doesn't require this feature. Here is the proof:

Suppose $A$ is NP-hard, and $f$ is a polynomial time reduction from $A$ to $B$ such that $x \in A$ iff $f(x) \in B$. Since $A$ is NP-hard, for every $L$ in NP there exists a polynomial time reduction $g$ such that $x \in L$ iff $g(x) \in A$, and so $x \in L$ iff $f(g(x)) \in B$. Since $x \mapsto f(g(x))$ is also polynomial time, this shows that $B$ is NP-hard.

At no point of this proof do we use anything about the possible instances produced by $f$.

---

Another situation in which we can conclude an improved result is when the instance (rather than the solution) has a specific form. Suppose, for example, that we were able to reduce HP to ST, and the resulting graph never has triangles (I'm not claiming that this is possible; this is just for illustration). In this case, we could conclude also that ST-for-triangle-free-graphs is also NP-hard. It still remains true that ST itself is NP-hard; if a special case is NP-hard, then the general case is a fortiori NP-hard.

Answer 2

To show the one direction you show that there is an algorithm that reduces one problem to another in polynomial time. If you reduce Hamiltonian Path to Spanning Tree, you always get spanning trees of some form (because that's how you construct HP instances in ST). You usually can't generate all ST instances via reduction from a HP problem.

So reduction is ANY HP to some ST where solution to ST is interpretation for solution for HP.

If you want to show that both are in the same complexity class, you'd want to show the reverse as well.

ANY ST to SOME HP where solution to HP is interpretation for solution for ST.