Optimization problem in a social network I would appreciate anybody's help with a problem I am trying to solve.


A little background:


given is a social network consisting of people represented as a directed graph, with edge from person A to person B if person A is a follower of pers B on that network. For any set S of people, we say that S reaches all people who are followers of at least one person in S. Everyone is a follower of themselves so any set of people S reaches at least itself


Problem:


The optimization version of this problem is as follows: given a social network and
a parameter k, compute the maximum possible number of people that can be directly reached
by up to k (observers).

The search version of the problem is to compute a set of up to k observers, which reaches the
maximum number of people.

Show that given a hypothetical algorithm for the decision version of the problem, both the
optimization and search versions of the problems can be solved with at most a polynomial
overhead (i.e., if the algorithm for the decision version takes O(T(n)) time on instances of size n then the optimization and search versions can be solved in O(T(n)c) time for some constant c).
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.