We study the complexity of determining a winning committee under the Chamberlin–Courant voting rule when voters’ preferences are single-crossing on a line, or, more generally, on a median graph (this class of graphs includes, e.g., trees and grids). For the line, Skowron et al. (2015) describe an \(\varvec{O}(\varvec{n}^{\varvec{2}}\varvec{mk})\) algorithm (where \(\varvec{n}\) , \(\varvec{m}\) , \(\varvec{k}\) are the number of voters, the number of candidates and the committee size, respectively); we show that a simple tweak improves the time complexity to \(\varvec{O(nmk)}\) . We then improve this bound even further by reducing our problem to the \(\varvec{k}\) -link path problem for complete DAGs with Monge-concave weights, obtaining an \(\varvec{O(n}^{\varvec{1 + o(1)}}\varvec{m})\) algorithm for arbitrary misrepresentation functions and a nearly linear algorithm for the Borda misrepresentation function. For trees, we point out an issue with the algorithm proposed by Clearwater et al. (2015), and develop an \(\varvec{O(nmk)}\) algorithm for this case as well. For grids, we formulate a conjecture about the structure of optimal solutions, and describe a polynomial-time algorithm that finds a winning committee if this conjecture is true; we also explain how to convert this algorithm into a bicriterial approximation algorithm whose correctness does not depend on the conjecture.
