# When talking about the length of a path in a graph, what exactly is a skip?

I'm studying for a final and when looking for the shortest path in a graph from one vertex to another, what is meant by k-skips?

One website defines it as the ability to change the weight of one edge to zero, as if you don't include it in the path distance.

Another one defines it as:

$P*$ is a k-skip shortest path from s to t, if it includes at least a vertex out of every k consecutive vertices in P

Which I can't seem to understand. I would appreciate some clarification in the matter.

## 1 Answer

The second definition that you quote is informal, and open to interpretation. Fortunately, the same paper On $k$-skip shortest paths by Tao, Sheng and Pei contains a formal definition, Definition 2 on page 4.

That said, $k$-skip is not a common term, and doesn't really have a universally accepted definition (or indeed, any universally known definition), except perhaps in work following up on the Tao et al. paper mentioned above.