Provenance embedding algorithms are well known for tracking the footprints of information flow in wireless networks. Recently, low-latency provenance embedding algorithms have received traction in vehicular networks owing to strict deadlines on the delivery of packets. While existing low-latency provenance embedding methods focus on reducing the packet delay, they assume a complete graph on the underlying topology due to the mobility of the participating nodes. We identify that the complete graph assumption leads to sub-optimal performance in provenance recovery, especially when the vehicular network is sparse, which is usually observed outside peak-hour traffic conditions. As a result, we propose a two-part approach to design provenance embedding algorithms for sparse vehicular networks. In the first part, we propose secure and practical topology-learning strategies, whereas in the second part, we design provenance embedding algorithms that guarantee ultra-reliability by incorporating the topology knowledge at the destination during the provenance recovery process. Besides the novel idea of using topology knowledge for provenance recovery, a distinguishing feature for achieving ultra-reliability is the use of hash-chains in the packet, which trade communication-overhead of the packet with the complexity-overhead at the destination. We derive tight upper bounds on the performance of our strategies, and show that the derived bounds, when optimized with appropriate constraints, deliver design parameters that outperform existing methods. Finally, we also implement our ideas on OMNeT++ based simulation environment to show that their latency benefits indeed make them suitable for vehicular network applications.