  We study the shortcut Fr\'{e}chet distance, a natural variant of the
Fr\'{e}chet distance, that allows us to take shortcuts from and to any point
along one of the curves. The classic Fr\'echet distance is a bottle-neck
distance measure and hence quite sensitive to outliers. The shortcut
Fr\'{e}chet distance allows us to cut across outliers and hence produces
significantly more meaningful results when dealing with real world data.
Driemel and Har-Peled recently described approximation algorithms for the
restricted case where shortcuts have to start and end at input vertices. We
show that, in the general case, the problem of computing the shortcut
Fr\'{e}chet distance is NP-hard. This is the first hardness result for a
variant of the Fr\'{e}chet distance between two polygonal curves in the plane.
We also present two algorithms for the decision problem: a 3-approximation
algorithm for the general case and an exact algorithm for the vertex-restricted
case. Both algorithms run in O(n^3 log n) time.
