Finding a set of hubs in a graph Suppose, we are given a graph $G = (V,E,d)$, where $V$ is the set of vertices, $E$ is the set of edges, and $d$ is a distance function $d: E \mapsto \mathbb{R^+}$. Let $S$ be the set of source vertices and $EX$ be the set of exit vertices in $G$. Further, we are given the integers $k, \gamma$ and $\delta$. A $(k, \gamma, \delta)$-hub is a set of vertices $H \subseteq V \setminus (S \cup EX)$ such that:


For any source vertex $s_i \in S$, there exists an exit vertex $t_j \in EX$ and a hub vertex $h_{ij} \in H$ such that $d(s_i,h_{ij}) \le \gamma$ and $d(h_{ij},t_j) \le \delta$,
$|H| \le k$, i.e., there are at most $k$ hub vertices.


Intuitively, a hub is a small set of vertices such that for any source vertex, there is a short path to some exit through an intermediate hub vertex.

An optimization problem is: given $\gamma$ and $\delta$, find the minimum $k$ such that there exists a $(k, \gamma, \delta)$-hub (or show that none exists). This problem is likely to be NP-hard, but I could not find a reduction from an existing NP-hard problem.

Is there any known hardness result or approximation algorithm for this problem?
Reduction

The decision version of your problem (where $k$ is given and we wish to know whether a hub exists for that $k$) is NP-hard by reduction from dominating set. 

Let $G = (V, E)$ be the given graph for the dominating set problem and let $k$ be the target number of vertices to be selected for the dominating set problem.

Then construct the instance of your problem (a graph $G'$, a distance function, a set of source vertices $S$, a set of exit vertices $EX$, a target number of hub vertices $k'$, and a pair of values $\gamma$ and $\delta$) as follows:


The new graph $G' = (V', E')$ has vertex set $V'$ and edge set $E'$.
$V' = V \times \{0,1,2\}$.
For all $v \in V$, $((v, 0), (v, 1))$ and $((v, 1), (v, 2))$ are edges in $E'$.
For all $(w, v) \in E$, $((w, 1), (v, 1))$ is an edge in $E'$.
No other edges are present in $E'$.
Every edge has length 1, so that the distance function is the standard undirected graph distance.
$S = V \times \{0\}$.
$EX = V \times \{2\}$.
$k' = k$.
$\gamma = \delta = 2$.


Correctness

The choice of a $(k', \gamma, \delta)$-hub is the choice of $k'$ vertices in $V' \backslash (S \cup EX)$ such that for every $v \in S$ there exists a chosen vertex within distance $\gamma$ of that vertex and a vertex $w \in EX$ within distance $\delta$ of that chosen vertex.

The instance generated by the reduction (when run on graph $G = (V, E)$ and value $k$) asks whether a $(k,2,2)$-hub exists. In that particular case, it is a question of whether there exists a choice of $k$ vertices in $V' \backslash (S \cup EX) = V \times \{1\}$ such that for every $v \in S = V \times \{0\}$ there exists a chosen vertex within distance $2$ of that vertex and a vertex $w \in EX = V \times \{2\}$ within distance $2$ of that chosen vertex.

But notice that any vertex that could be a hub vertex is of the form $(v, 1)$, and therefore has distance one from exit vertex $(v, 2)$. The part of the condition requiring a nearby exit vertex is then automatically satisfied.

Thus the instance is a "yes" instance if and only if there exists a choice of $k$ vertices in $V' \backslash (S \cup EX) = V \times \{1\}$ such that for every $v \in S = V \times \{0\}$ there exists a chosen vertex within distance $2$ of that vertex. This occurs if there exists a choice of $k$ vertices $C \subseteq V$ such that for every $v \in V$ there exists some $c \in C$ with $d((v, 0), (c, 1)) \le 2$. 

But $d((v, 0), (c, 1)) \le 2$ if and only if $c$ and $v$ are equal or neighbors in $G$. Thus we can rewrite the condition for the problem instance to be a "yes" instance as follows: there exists a choice of $k$ vertices in $V$ such that every vertex in $V$ is either adjacent to a chosen vertex or is chosen itself. This is exactly the "yes" condition for the dominating set instance, proving this reduction to be answer preserving.

Since the reduction is clearly polynomial time, this concludes the proof that your problem is NP-hard.