Low-latency provenance embedding methods have received traction in vehicular networks for their ability to track the footprint of information flow. One such known method is based on Bloom filters wherein the nodes that forward the packets appropriately choose a certain number of hash functions to embed their signatures in a shared space in the packet. Although Bloom filter methods can achieve the required accuracy level in provenance recovery, they are known to incur higher processing delay since higher number of hash functions are needed to meet the accuracy level. Motivated by this behaviour, we identify a regime of delay-constraints within which new provenance embedding methods must be proposed as Bloom filter methods are no longer applicable. To fill this research gap, we present network-coded edge embedding (NCEE) protocols that facilitate low-latency routing of packets in vehicular network applications. First, we show that the problem of designing provenance recovery methods for the NCEE protocol is equivalent to the celebrated problem of compressed sensing, however, with additional constraints of path formation on the solution. Subsequently, we present a family of path-aware orthogonal matching pursuit algorithms that jointly incorporates the sparsity and path constraints. Through extensive simulation results, we show that our algorithms enjoy low-complexity implementation, and also improve the path recovery performance when compared to path-agnostic counterparts.