Note that while the special edge e * ,∅ is needed for the direct correspondence with the ILP score, its weight is constant across variable assignments.
this edge only adds a constant offset of c ∅ * to the ILP solution.