# Highway dimension

I'm interested in understanding some recent theoretical results on pathfinding. Specifically this paper:

http://research.microsoft.com/apps/pubs/default.aspx?id=201061

I understand from the paper that in certain types of graphs (road networks for example) a small set of nodes are sufficient to cover a large number of shortest paths. I also understand that the size of the hitting set that forms such a cover can differ from node to node but is upper bounded by some integer h which is called the highway dimension of the graph.

Two questions:

i) The concept of highway dimension is defined in this paper (Defi 3.4, page 5) using a distance parameter r and a hitting set H which exists for every vertex v in the graph. Specifically, the authors say (slightly paraphrasing) "for all r > 0 and all v there exists a H whose size is bounded by h (the highway dimension of the graph)"

I don't know how to interpret this: is the highway-dimension h constant for all tuples (r, v) or does the value depend on the choice of r? I tend toward the former interpretation but the paper seems ambiguous on this point.

ii) The definition also makes reference to paths P of length > r which can be reached from the vertex v with distance no more than 2r. I don't understand the significance of the (r, 2r) construction. Would it not be simpler to construct a hitting set that covers all paths which begin at v and have length > r? What is gained by this more complicated definition?

• I think the paper is clear on pt i). To put it another way, let $h_{v,r}$ be the size of the smallest hitting set satisfying the requirements for $v$ and $r$. Then the dimension $h$ is $\min_{v,r}{h_{v,r}}$ Aug 20 '14 at 16:37
• Hi Sasho. My understanding is that h is a maximum cardinality chosen by evaluating all minimum hitting sets. Anyway, if I understand your reply, you are saying h is computed for all (v, r) hitting sets. Is that right? This interpretation seems to fit with my reading. Thanks! Any thoughts re question (ii) ? Aug 21 '14 at 5:34
• I meant to say $\max_{v,r} h_{v,r}$ not min, by the way. For question ii) I don't have time now to study the paper in sufficient detail to answer. Aug 21 '14 at 15:45