A relaxed Steiner Tree Problem Given a weighted graph $G(V,E,w)$ where $w$ is the weight function on edges and a subset of vertices $S\subseteq Q$ called terminals, a Steiner Tree is a connected subgraph which connects all vertices in $S$. Finding minimum weight Steiner Tree is called Minimum Steiner Tree Problem. This problem and many of its variants are known to be NP-Complete. 



I thought about this variant where we dont need to connect all vertices in $S$. That is, along with the input, we are also given a natural number $k$, such that $k&lt;|S|$. Now, find a minimum weight connected subgraph which connects at least $|S|-k$ vertices in $S$. 

Notice that when $k$=0, this is the usual Steiner Tree Problem and when $k=|S|-2$, it is Shortest path problem. Is this problem NP-Complete for any arbitrary $k$?

I do not know whether this question already exists (quite possible considering the number of variants of Steiner Tree Problem). I did a brief search and I couldnt find anything related to this problem.
Some observations:

First, let's take a different parameter called c. The problem is to find a minimum weight connected subgraph which connects at least c vertices in S. Now c=2 is the easy problem you refer to, and c=|S| is the Steiner tree problem.

I think for c=$|S|^\epsilon$, the problem is still NP-hard. The reduction would basically add lots of useless terminals connected to the rest of the graph with very high edge weights, so that these vertices will never be picked in the min weight tree, and the min weight tree will only have the vertices we wanted. For example, an algorithm to solve this problem for c=|S|/2 can be used to solve the Steiner tree problem by just taking the instance of Steiner tree, and doubling the number of terminals and connecting them to the rest of the graph with large edge weights.

As you mentioned, the c=2 case is in P. Similarly, for any constant c', the c=c' case is easy by a brute force search.