# What is the usage of a decision problem for an optimization problem like the longest path problem?

I just read this definition for the longest path problem:

LONGEST PATH
Input: A graph $$G=(V,E)$$, an integer $$k$$.
Question: Is there a path with at least $$k$$ vertices in $$G$$

This seems a decision problem and a certificate can be verified easily. But, what is the usage of such a problem? Isn't the main concern finding the longest path in the graph? I guess that would be an optimization problem, and verifying a given certificate can't be done in polynomial time, so that is not $$NP$$. right?

If yes, then what is the usage of the decision problem (which is $$NP$$) and what is its relation to the main problem?

My question is different from "NP-complete" optimization problems because I also asked about the relationship between a decision problem and a relevant optimization problem, and how a decision problem may help us in solving the optimization problem, and basically what is their usage in such cases.

Let's take your example of Longest Path. We know that the longest path has length between 1 and $$n$$ (where $$n$$ is the number of vertices), so we can find the actual length of the longest path by doing binary search using a series of queries of the form "Is there a path of length at least $$n/2$$?", "... $$3n/4$$?", ... That tells us that the longest path has some length $$\ell$$. Now, we can loop through the edges one by one. Delete the $$i$$th edge and ask, "Is there still a path of length at least $$\ell$$?" If there is, go on to the next edge; if there isn't, undelete edge $$i$$ and go on to the next one. When this algorithm terminates, we'll be left with a graph that is exactly a path of length $$\ell$$. We used $$\Theta(\log n$$) calls to Longest Path to find the length of the longest path, and $$O(n^2)$$ calls to find the actual path.