DOI: 10.1145/3133244 Dennis Shasha
ing to cross through red towns.
Challenge: So far, we have considered
only a very simple configuration of towns;
now consider that the red and blue towns
alternate like the squares of a four-by-four
checkerboard. Every town is connected
to all its vertical and horizontal neighbors. You may build eight new roads between diagonally neighboring towns.
Where should the roads go? And af-
ter the roads are built, which towns
should swap populations to minimize
the number of swaps needed to achieve
partitioned peace, where the swaps are
between towns directly connected by
without crossing through blue towns.
Likewise, the blue town dwellers can
travel to other blue towns without hav-
IN A MYTHICAL land of rhetorically encouraged antagonism, different factions manage to co-exist, though poorly.
Imagine a set of red and blue hill towns
connected by a network of roads. People
in the red towns deal well with one another. People in the blue towns deal well
with one another. But when a person
from a red town travels through a blue
town or vice versa, things can get unpleasant. The leaders of the red and the
blue towns get together and decide the
best way to resolve their differences is to
perform a series of swaps in which the
inhabitants of k red towns swap towns
with the inhabitants of k blue towns
with the end result that a person from a
blue town can visit any other blue town
without passing through a red town and
likewise for a person from a red town.
We call such a desirable state “
partitioned peace.” The goal is to make k as
small as possible.
Warm-Up 1. Given the configuration
in the figure here, what is the minimum
number of swaps needed to achieve partitioned peace?
Solution to Warm-Up 1. Two swaps
are sufficient: Red_ 1 with Blue_ 7 and
Red_ 3 with Blue_ 4.
Because exchanging town populations is painful for the people who must
move, the leaders seek other arrangements; they are willing to build, for example, a certain number of roads to reduce the number of swaps.
Warm-Up 2. Given the configuration in the figure, what is the minimum
number of swaps needed to achieve partitioned peace if you were able to build a
single new road?
Solution to Warm-Up 2. Build a road
between Blue_ 7 and Red_ 1 and then
swap Red_ 1 with Blue_ 4. The red town
dwellers can travel to other red towns
What is the minimum number of towns you can exchange so red and blue travelers never
need to cross the other color’s towns?
[CONTINUED ON P. 111]
Can you create
an algorithm that
will perform a
of swaps to achieve