Characterizing acyclic graphs by labeling edges

In this paper two new characterizations of acyclic graphs are introduced. Additionally, restricted versions of them are also proposed to address some important special cases. These restricted characterizations, in turn, were used to obtain new integer programming formulations for some associated relevant NP-hard problems. Resulting formulations are compact, in the sense that the number of variables and constraints they contain are polynomially bounded. One of them, in particular, that for the homogeneous version of the Probabilistic Minimum Spanning Tree Problem, under a MILP solver, is used here to obtain, for the first time, proven optimal solutions to that problem.