Abstract: In order to reduce the probe cost and improve the accuracy of the inference algorithm of the link loss rate, a novel link loss rate inference algorithm is proposed based on minimal cover set. This algorithm reduces the number of the end-to-end paths by reducing the rank of the routing matrix that caused by the minimal cover set measurements. On the other hand, the accuracy of the algorithm is improved by the implement of the solving linear equations and Gibbs sample. Simulation results show that this algorithm can obtain a higher accuracy with less end-to-end measurement paths.