POPULAR SPANNING TREES
Combinatorial Optimization is combined with Social Choice Theory when the goal is to decide on the quality of a spanning tree of an undirected graph. Given individual preferences over the edges of the graph, spanning trees are compared by means of a Condorcet criterion. The comparisons are based on scoring functions used in classic voting rules such as approval voting and Borda voting. In this work, we investigate the computational complexity involved in deciding on the quality of a spanning tree with respect to the different voting rules adapted. In particular, we draw the sharp separation line between polynomially solvable and computationally intractable instances.
spanning trees social choice computational complexity