Let G be a graph of order n. Let lpt(G) be the minimum cardinality of a set X of vertices of G such that X intersects every longest path of G and define lct(G) analogously for cycles instead of paths. We prove that (i) lpt(G) ≤ ceiling(n/4-n^{2/3}/90), if G is connected, (ii) lct(G) ≤ ceiling(n/3-n^{2/3}/36), if G is 2-connected, and (iii) lpt(G) ≤ 3, if G is a connected circular arc graph. Our bound on lct(G) improves an earlier result of Thomassen and our bound for circular arc graphs relates to an earlier statement of Balister et al. the argument of which contains a gap. Furthermore, we prove upper bounds on lpt(G) for planar graphs and graphs of bounded tree-width.