patternMinor
Why is Steiner Tree trivially in NP?
Viewed 0 times
steinertriviallywhytree
Problem
I'm learning about NP-completeness, and many reduction proofs start off by stating that a problem is triviallyin NP. But I can't seem to wrap my head around this.
Why is this so?
Why is this so?
Solution
What is normally meant in cases like this is
there is a simple, obvious algorithm which demonstrates that the problem is in $\mathcal{NP}$,
with an implicit
but we don't have enough space, can't be bothered, or don't want to bore the reader by including it.
Whether it really is trivial is a trickier thing (but often it really is).
Before returning to the Steiner Tree problem, recall the two common definitions of $\mathcal{NP}$ membership:
So for the Steiner Tree problem (remember we only concern ourselves with the decision versions), they are saying that at least one of the following is true:
-
Given a graph, a set of required points, a value $k$ and a tree (the alleged solution), we can easily check that the tree is a Steiner tree of value at most $k$, or
-
Given a graph, a set of required points and a value $k$, we can easily compute a Steiner tree of value at most $k$ if we can make some really good guesses.
Hopefully in this case both of these should be more obviously true. In the first case, we need only check that the tree1 contains the required points, and the total weight of the tree is at most $k$. In the second, we can use the magic of non-determinism to guess which edges are in the tree, then check that it's okay as in the first case.
The only further requirement is that these procedures be computable in polynomial time, but in both cases we at most need to look at each edge of the graph and each vertex of the graph once(-ish) (if we have sensible data structures to store the graph and tree), so even without being too precise, we can see that they can both be done in polynomial time.
Footnotes.
there is a simple, obvious algorithm which demonstrates that the problem is in $\mathcal{NP}$,
with an implicit
but we don't have enough space, can't be bothered, or don't want to bore the reader by including it.
Whether it really is trivial is a trickier thing (but often it really is).
Before returning to the Steiner Tree problem, recall the two common definitions of $\mathcal{NP}$ membership:
- A problem is in $\mathcal{NP}$ if, given the input and a solution, we can check that the solution is correct in deterministic polynomial time, or
- given the input, we can compute the solution in non-deterministic polynomial time.
So for the Steiner Tree problem (remember we only concern ourselves with the decision versions), they are saying that at least one of the following is true:
-
Given a graph, a set of required points, a value $k$ and a tree (the alleged solution), we can easily check that the tree is a Steiner tree of value at most $k$, or
-
Given a graph, a set of required points and a value $k$, we can easily compute a Steiner tree of value at most $k$ if we can make some really good guesses.
Hopefully in this case both of these should be more obviously true. In the first case, we need only check that the tree1 contains the required points, and the total weight of the tree is at most $k$. In the second, we can use the magic of non-determinism to guess which edges are in the tree, then check that it's okay as in the first case.
The only further requirement is that these procedures be computable in polynomial time, but in both cases we at most need to look at each edge of the graph and each vertex of the graph once(-ish) (if we have sensible data structures to store the graph and tree), so even without being too precise, we can see that they can both be done in polynomial time.
Footnotes.
- As A. Schulz notes in the comments, there is an additional issue of ensuring that the witness (the solution handed to us) has an encoded length bounded by a polynomial in the size of the original input. This may be easy to see, but as A. Schulz also notes, if we're talking about the Geometric Steiner Tree problem, then we might have to make an additional argument about how we encode the geometry of the tree - not necessarily too complicated, but still important. If we're talking about the Steiner Tree Problem in Graphs, then it's more straightforward (as we don't have to worry about the geometry), and perhaps something you can gloss over. Nonetheless it is important to be careful :).
Context
StackExchange Computer Science Q#33715, answer score: 9
Revisions (0)
No revisions yet.