Uncertainty reduction has recently been introduced in the robust optimization literature as a relevant special case of decision-dependent uncertainty. Herein, we first show that when the uncertainty reduction is constrained, the resulting optimization problem is NP-hard. We further show that relaxing these constraints leads to solving a linear number of deterministic problems in certain special cases. We provide insights into possible MILP reformulations and illustrate the practical relevance of our theoretical results on the shortest path instances from the literature.