Example: Consider the problem SHORTEST-PATH that finds a shortest path
between two given vertices in an unweighted, undirected graph *G = (V,
E)*. An instance of SHORTEST-PATH consists of a particular graph and
two vertices of that graph. A solution is a sequence of vertices in the
graph, with perhaps an empty sequence denoting that no path exists. Thus
the problem SHORTEST-PATH is a relation that associates each instance of
a graph and two vertices with a solution (namely a shortest path in this
case). Note that a given instance may have no solution, exactly one solution,
or multiple solutions.

A decision problem PATH related to the SHORTEST-PATH problem above is
: Given a graph *G = (V, E)*, two vertices u, vV,
and a non-negative integer k, does a path exist in G between u and v whose
length is at most k ?

Note that the decision problem PATH is one way of casting the original optimization problem as a decision problem. We have done this by imposing a bound on the value to be optimized. This is a popular way of transforming an optimization problem into a decision problem.

If an optimization problem is easy then its related decision problem is easy as well. Similarly, if we can provide evidence that a decision problem is hard, we also provide evidence that its related optimization problem is hard.