  \textit{Voronoi game} is a geometric model of competitive facility location
problem played between two players. Users are generally modeled as points
uniformly distributed on a given underlying space. Each player chooses a set of
points in the underlying space to place their facilities. Each user avails
service from its nearest facility. Service zone of a facility consists of the
set of users which are closer to it than any other facility. Payoff of each
player is defined by the quantity of users served by all of its facilities. The
objective of each player is to maximize their respective payoff. In this paper
we consider the two players {\it Voronoi game} where the underlying space is a
road network modeled by a graph. In this framework we consider the problem of
finding $k$ optimal facility locations of Player 2 given any placement of $m$
facilities by Player 1. Our main result is a dynamic programming based
polynomial time algorithm for this problem on tree network. On the other hand,
we show that the problem is strongly $\mathcal{NP}$-complete for graphs. This
proves that finding a winning strategy of P2 is $\mathcal{NP}$-complete.
Consequently, we design an $1-\frac{1}{e}$ factor approximation algorithm,
where $e \approx 2.718$.
