Finding a set of hubs in a graph

Question

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?

Answer 1

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.

Answer 2

In my first answer, I addressed the NP-hardness of this problem. Here I address the approximability.

Overview

Below, we reduce the Hub problem to the Set Cover problem such that the choice of sets in the Set Cover instance corresponds with a choice of hub vertices. Then any approximation algorithm for Set Cover can be used to approximate this problem (to within the same factor) simply by following the reduction, approximating the resulting Set Cover instance, and outputting a selection of hub vertices which corresponds with the selection of sets in the chosen set cover.

For completeness, we also reduce Set Cover to the Hub problem such that the choice of sets in the Set Cover instance corresponds with a choice of hub vertices. In much the same way, this proves that any approximation algorithm for the Hub problem can be used to approximate Set Cover to within the same factor.

Thus the Hub problem is approximable within some factor in polynomial time if and only if Set Cover is approximable within that factor in polynomial time.

Under the assumption that $P \ne NP$, Set Cover is not approximable within a factor of $(1-o(n))\cdot \ln n$ where $n$ is the number of elements in the universe (according to wikipedia: https://en.wikipedia.org/wiki/Set_cover_problem#Inapproximability_results). Since under the reductions below every element in the universe corresponds with a start vertex, the Hub problem is inapproximable within a factor of $(1-o(n))\cdot \ln n$ where $n$ is the number of start vertices.

On the other hand, if a $\Theta(\ln n)$-approximation (where $n$ is the number of start vertices) is of interest, this is certainly possible. In particular, an explicit approximation algorithm for the Hub problem can be constructed out of any approximation algorithm for Set Cover together with the Hub Problem -> Set Cover reduction provided below. Any $\Theta(\log n)$-approximation algorithm for Set Cover from the literature would serve.

Hub Problem -> Set Cover reduction

For this reduction, we start with an instance of the Hub Problem. This consists of a graph $G = (V, E)$, an assignment of lengths to the edges, a partition of $V$ into start vertices, exit vertices, and vertices that could be hubs, and values $\gamma$ and $\delta$.

First conduct an All-Pairs Shortest Paths search to compute the distance between every pair of vertices. If we replace the given graph with a complete graph whose edge lengths are the shortest path distances, the problem clearly remains the same. The benefit of doing this is that removing a vertex (and all of the edges incident on it) will not affect the distance between any two other vertices. Thus if we are certain that a potential hub vertex will not be chosen as a hub, we can remove the vertex while preserving the answer to the problem.

Conduct a breadth first search of all of the vertices starting at all of the exit vertices that searches to distance $\delta$. This allows us to quickly split the vertices of the graph into two groups: the vertices within distance $\delta$ of at least one exit vertex and the vertices that are a distance of greater than $\delta$ from every exit vertex. Any potential hub vertex in the second group can never serve as a hub between a start vertex and an exit vertex since the exit vertex will be a distance of more than $\delta$ away from the hub. Thus it is never necessary to select a vertex in this second group as a hub. As a result, we can remove all of those vertices from the graph while preserving the answer to the problem.

If we do that, we find that every remaining potential hub vertex will be within distance $\delta$ of at least one exit vertex. Then it is sufficient to select a set of hubs such that every start vertex is within a distance of $\gamma$ of that hub. If we do that, clearly every start vertex will be within a distance of $\gamma$ of a hub that is within a distance of $\delta$ of an exit vertex.

But then, if we remove all the exit vertices and also remove the constraint regarding exit vertices, the answer to the problem will remain the same.

At this point, we are left with a complete graph on some set of vertices that can be partitioned into start vertices and potential hubs. Each edge has some length, and we wish to select vertices from among the potential hubs such that every start vertex is within distance $\gamma$ of a selected hub.

Note that since the distance between two vertices is the length of the edge between them, we have a very quick way of determining whether a start vertex and a potential hub have distance at most $\gamma$.

Now we construct an equivalent Set Cover instance. The universe being covered consists of $n$ elements where $n$ is the number of start vertices. There are $m$ sets with which we could cover this universe, where $m$ is the number of potential hubs. Each element in the universe is associated with a start vertex and each set is associated with a potential hub. In particular, the set associated with a given potential hub consists exactly of the set of elements associated with those start vertices that are within a distance of $\gamma$ of the given potential hub.

Clearly, since shortest paths, breadth first search, and removal of vertices from a graph are all polynomial time operations, this reduction is polynomial time.

Furthermore, as argued, the original problem is equivalent to the problem of choosing hubs in the final bipartite graph (with parts for start vertices and parts for potential hubs) such that each start vertex is within range of a chosen hub. The reduction maps the potential hubs to the sets and the start vertices to the elements: the Set Cover instance requires a choice of sets (potential hubs) such that each element (start vertex) is contained in (within $\gamma$ of) at least one chosen set (hub).

Thus the reduction is answer preserving.

As we see the reduction is polynomial time and answer preserving. In addition, the choices of hub vertices correspond with choices of sets and $n$ corresponds with the number of start vertices, as claimed in the overview.

Set Cover -> Hub Problem reduction

For this reduction, we start with an instance of Set Cover consisting of universe $\{1,..., n\}$ and a list of sets $S_1, S_2, ..., S_m$ with $S_i \subseteq \{1,..., n\}$.

We wish to construct an instance of the Hub problem such that the number of hub vertices necessary to create a hub is equal to the number of sets $S_i$ necessary for their union to be the entire universe.

Construct the instance as follows:

• $G = (V,E)$ has vertex set $V$ and edge set $E$.
• $V = \{(1, 0), (2, 0), ..., (m, 0)\} \cup \{(1, 1), (2, 1), ..., (m, 1)\} \cup \{(1, 2), (2, 2), ..., (n, 2)\}$
• For all $i \in \{1, ..., m\}$, $((i,0),(i,1))$ is an edge in $E$.
• For all $i \in \{1, ..., m\}$ and $j \in \{1, ..., n\}$, $((i,1),(j,2))$ is an edge in $E$ if and only if $j \in S_i$.
• No other edges are present in $E$.
• Every edge has length 1, so that the distance function is the standard undirected graph distance.
• $S = \{(1, 2), (2, 2), ..., (n, 2)\}$.
• $EX = \{(1, 0), (2, 0), ..., (m, 0)\}$.
• $\gamma=\delta=1$.

Clearly this instance can be constructed in polynomial time.

Since every vertex that could be a hub vertex (the ones of the form $(i, 1)$) is within distance one of an exit vertex (in particular $(i, 0)$), the only constraint that the Hub problem imposes that is not automatically satisfied is that every start vertex must be within distance one of at least one hub vertex. In other words, every start vertex must be adjacent to a hub vertex.

Thus the Hub problem instance is equivalent to the problem of choosing vertices among $\{(1, 1), (2, 1), ..., (m, 1)\}$ such that each vertex in $\{(1, 2), (2, 2), ..., (n, 2)\}$ is adjacent to at least one chosen vertex. But $(j, 2)$ is adjacent to $(i, 1)$ if and only if $j \in S_i$. Thus the Hub problem instance is equivalent to the problem of choosing values among $\{1, 2, ..., m\}$ such that each value in $\{1, 2, ..., n\}$ is in $S_i$ for at least one chosen $i$. This is exactly the Set Cover instance.

Thus the reduction is answer preserving.

As we see the reduction is polynomial time and answer preserving. In addition, the choices of hub vertices correspond with choices of sets and $n$ corresponds with the number of start vertices, as claimed in the overview.