7
$\begingroup$

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<|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.

Improve this question
$\endgroup$

4 Answers 4

Reset to default
5
$\begingroup$

As in Robin's answer, I'll use the parameter $c$ to denote the minimum number of terminals that we are required to connect. Robin's response already answers your question for most values of $c$, but if you're willing to make some additional assumptions then we can narrow or eliminate the gap: if we assume that NP-complete problems cannot be solved in time $2^{O(f(n))}$ for some function $f(n)$ then $c = O(f(n)/\log n)$ cannot be NP-complete.

First, if $c = \Omega(n^\epsilon)$ for some $\epsilon$, then the problem is NP-complete as already explained: we could solve normal Steiner tree by adding a polynomial number of dummy terminals that would be very expensive to connect.

Note that a Steiner tree is uniquely determined by it's terminals and Steiner nodes of degree at least 3 (we can complete the graph with shortest path distances and replace Steiner nodes of degree 2 by the edge between its 2 neighbors). Since all leaves must be terminals, an optimal solution with $c$ terminals can only have $O(c)$ Steiner nodes. Therefore we can find the optimal solution by brute-force in time $n^{O(c)} = 2^{O(c\log n)}$. If $c = O(f(n)/\log n)$, and solving NP-complete problems requires $2^{\Omega(f(n))}$ then these instances cannot be NP-complete (although they may not be in P).

In particular, if NP does not have quasi-polynomial time algorithms then $c = O(\textrm{polylog}(n))$ is not NP-hard, and if NP does not have sub-exponential time algorithms then $c = o(n^\epsilon)$ is not NP-hard, in which case the transition to NP-completeness is at $c = \theta(n^\epsilon)$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Since you assumed that NP does not have quasi-polynomial time algorithms, I'd like to add that if we choose a stronger hypothesis, like the exponential time hypothesis, that would narrow the gap even further. $\endgroup$
    – Robin Kothari
    Sep 8, 2010 at 1:51
  • $\begingroup$ True, and the gap can be eliminated if NP does not have sub-exponential algorithms. I've updated the answer to be parameterized by an arbitrary assumption of the time required to solve NP-complete problems. $\endgroup$
    – Ian
    Sep 8, 2010 at 2:29
8
$\begingroup$

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.

Improve this answer
$\endgroup$
4
$\begingroup$

This problem is hard even when S is the whole vertex set. That special case is the k-MST problem. There are known approximation algorithms for it (there is a factor 2 by Garg), and they would generalize to given constant factor approximations for this problem.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Interesting.. Thanks for pointing it out. $\endgroup$
    – Radhe
    Sep 8, 2010 at 16:47
0
$\begingroup$

If I can solve your problem, I can solve the Steiner Tree problem by setting k = 0. So why wouldn't this be NP-Complete?

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ The problem is easy for some values of k, and NP-complete for other values: as I understand the question, it is asking for which k it is NP-complete. $\endgroup$
    – András Salamon
    Sep 7, 2010 at 17:56
  • $\begingroup$ I guess I did not phrase the question properly.. Ya, as Andras Pointed out, the problem is NP-Complete for some values of $k$ and poly time for some values. But what about other values of $k$, esp if $k$ is a function of |S|? $\endgroup$
    – Radhe
    Sep 8, 2010 at 3:12

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.