A note on maximizing the minimum voter satisfaction on spanning trees

A fair spanning tree of a graph maximizes the minimum satisfaction among individuals given their preferences over the edges of the graph. In this note we answer an open question about the computational complexity of determining fair spanning trees raised in Darmann et al. (2009). It is shown that the maximin voter satisfaction problem under choose-t elections is NP-complete for each fixed t≥2.