Gerrymanderingis the practice of carving up electoral districts in very careful ways so as to lead to outcomes that favor a particular poetical

party. Recent court challenges to the practice have argued that through this Calculated redistric~g, large numbers of voters are being effectively (and intentionally) disenfranchised.

Computers, it turns out, have been implicated as the source of some of the "villainy" in the news coverage on this topic: Thanks to powerful software, gerrymandering has changed from an activity carried out by a bunch of people with maps, pencil, and paper into the industrial-strength process that it is today. Why is gerrymandering a computational problem? There are database issues involved in tracking voter demographics down to the level of individual streets and houses; and there are algorithmic issues involved in grouping voters into districts. Lets think a bit about what these latter issues look like.

Suppose we have a set of n precincts P~, P2 ..... Pa, each containing m registered voters. Were supposed to divide thes~e precincts into two districts, each consisting of r~/2 of the precincts. Now, for each precinct, we have information on how many voters are registered to each of two political parties. (Suppose, for simplicity, that every voter is registered to one of these two.) Well say that the set of precincts is susceptible to gerrymandering ff it is possible to perform the division into two districts in such a way that the same party holds a majority in both districts.

Give an algorithm to determine whether a given set of precincts is susceptible to gerrymandering; the running time of your algorithm should be polynomial in n and m.

Example. Suppose we have n = 4 precincts, and the following information on registered voters.

1. 2. 3. 4

A. 55. 43. 60. 47

B. 45. 57. 40. 53

This set of precincts is susceptible since, if we grouped precincts 1 and 4 into one district, and precincts 2 and 3 into the other, then party A would have a majority in both districts. (Presumably, the "we" who are doing the grouping here are members of party A.) This example is a quick illustration of the basic unfairness in gerrymandering: Although party A holds only a slim majority in the overall population (205 to 195), it ends up with a majority in not one but both districts