This is the classical problem of chain decomposition of partially ordered set (poset), in the sense that they can be reduced to each other very easily.
Any directed acyclic graph (DAG) $G(V,E)$ defines a poset $P(V, \preceq)$ naturally by $u\preceq v$ for any pair of vertices $(u,v)$ such that there is a path from $u$ to $v$ in $G$. A path (which is named traversal in the question) in $G$ corresponds to a chain in $P$ naturally. A set of paths whose union covers all vertices means exactly that the corresponding set of chains is a not-necessarily-disjoint chain decomposition of $P$.
Note that it is straightforward to modify a not-necessarily-disjoint chain decomposition of $P$ to a disjoint chain decomposition of $P$. Conversely, we can insert vertices between the vertices that correspond to a chain in $P$ so that they become a path in $G$.
There are efficient algorithms to compute a chain decomposition of a poset such as On the Decomposition of Posets by Yangjun Chen
and Yibin Chen, 2012. In that paper a poset is, in fact, given by a DAG in the first place.
This is the perfect time to present the very nice Dilworth's theorem: for any finite poset the largest antichain has the same size as the smallest chain decomposition.
It says that, for the situation in the question, the minimum number of traversals needed to cover all cities is the maximum number of cities that are pairwise unreachable to one another. Note that New York and Pittsburgh are not reachable from each other.