Optimization problem in a social network
The optimization version can be solved with logarithmic overhead by binary searching on the range $[0,\dots, n]$ of the possible values of $k$, where $n$ is the number of nodes of the input graph.

The search version of the problem can be solved with a polynomial overhead by first solving the optimization problem to obtain the maximum number $m$ of people than can be reached by $k$ observers and then:


guessing an observer $v$ in the input graph $G$,
computing the set $R$ of vertices than can be reached by $v$, and
checking whether $k-1$ observers are enough to reach $m-|R|$ people: if this is the case, then the problem is equivalent to the one of selecting $k-1$ observers in $G-R$, and the whole procedure can be repeated. Otherwise, try with a different vertex $v$.


Solving an instance of your problem when $k=0$ is trivial.

At most $n$ attempts are necessary to guess the right vertex, and the whole procedure is repeated most $k$ times, i.e., the decision problem needs to be solved at most $O(\log n + nk) = O(nk)$ times.