# 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}}$ – Sasho Nikolov 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) ? – Daniel 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. – Sasho Nikolov Aug 21 '14 at 15:45

## 1 Answer

I think highway dimension is a formalization of a physical property for roadmaps.

Assume that you have a large country. You want to get from one small city to another one. If the cities are far enough from each other, than you can assume that the route between them goes through one of the biggest city of the country. So it make a sense to add all large cities to hub labeling for all small ones.

Now we've connected all small cities which are on a big distance from each other. Consider smaller region and make the same step. Find all large cites for the region and add them to all cities there. The maximum over all regions and subregions is the highway dimension.

I think authors used balls as a convenient formalization of regions. For example, you can use some facts on covering graph with balls to provide a small hub labeling system.