0
$\begingroup$

I want to prove that the hardness of the Steiner tree problem lies in determining the optimal subset of Steiner vertices that need to be included in the tree and I need to show this by proving that if this set is provided, then the optimal Steiner tree can be computed in polynomial time.

It is clear that we can find an MST on the union of this set and the set of required vertices with Kruskal algorithm, and by contradiction proof, can be said that if this union of sets didn't give the MST so the subset of Steiner vertices is not the optimal subset. Any hints or tips would be appreciated.

|cite|improve this question
$\endgroup$
  • $\begingroup$ The way you prove something is by writing down a sequence of steps, where each step follows from the previous one. Just saying "it is obvious" is not a proof; try to imagine someone else who doesn't find it obvious, and think about how you would convince them. Your "by contradiction proof" makes no sense to me; I don't see how the follows -- it is just a restatement of what you need to prove. I suggest you spend more time trying to think about how to prove your claim in a step-by-step way. $\endgroup$ – D.W.♦ Jun 15 '17 at 17:35
  • $\begingroup$ @D.W. Thanks to your answer, I have just an idea to prove it, showing that the output MST(given in polynomial time) is equal to the OPT(optimal solution for the original problem)?? Is it true?? $\endgroup$ – NedaHn Jun 18 '17 at 10:50
0
$\begingroup$

It can be proved as I mentioned with contradiction, assume that $S1$ is the optimal subset of steiner nodes and $R$ is the required nodes, so we give the subgraph of main graph including $S1$ and $R$ nodes and the edges between them to Kroskal algorithm then we have a MST for them, we assume that it is not equal to OPT (solution for steiner tree problem), so the given subset (S1) was not optimal I mean at least one steiner node was not given or was given falsly.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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