Suppose you’re designing a planet for a computer game. You’ve already divided its surface into sectors, with at most three sectors meeting at any point, and you decide to place cities at some of the points where triples of sectors meet. Is there a way of assigning some of the sectors to be continents and others to be oceans in such a way that all your cities are on the coast?

A planet with four cities and four sectors

The abstract combinatorial problem underlying this planet design problem comes with a somewhat intimidating name, “planar monotone not-all-equal 3-sat”. In reverse order: it’s a form of 3-sat because you are trying to satisfy constraints on triples of sectors, and each sector has a binary value (land or water). It’s not-all-equal 3-sat because, in order for a city to be on the coast, the three sectors meeting there must not all be the same type. It’s planar because the surfaces of most planets are topological spheres, which is more or less the same as a plane for the purposes of this problem. And it’s monotone because…well, that one’s harder to explain. It comes from viewing the type of each sector as a Boolean variable and the cities as a certain kind of Boolean gate (with three inputs, producing a true output if they’re not all the same and false otherwise). The circuit you get from this interpretation has no not-gates. One way to get a non-monotone version of the same problem would be to add more cities, on borders between two sectors rather than three. Those would force the two sectors to be of opposite types, acting like a not gate.

Anyway, if you’re used to 3-sat being one of the canonical NP-complete problems, it may come as a surprise that planar not-all-equal 3-sat has a polynomial solution. The proof of the general case is short but a little messy, but in the planet design problem it’s much easier, at least in the case where all triples of sectors are cities. At each city, you have to decide which of its three sector boundaries is to be land-land or water-water. The chosen boundaries connect pairs of cities, forming a perfect matching. And if you can choose some of the boundaries in any way that perfectly matches the cities, the remaining boundaries can be used to separate land from water and solve the problem. (This is where we’re using the assumption that the planet’s suface is spherical rather than a torus or higher-genus surface: on a torus, the remaining boundaries might not separate land from water.) So all we have to do is apply a perfect matching algorithm to the graph whose vertices are cities and whose edges are sector boundaries.

In the case where some triples of sectors do not have cities on them, it’s a little more complicated, because two or three land-land or water-water boundaries can meet at those points. The usual proof goes through two levels of translation, but I think it’s easier to skip one of the levels (max cut) and go directly to the second one (the maximum weight even-degree subgraph). To do so, give each sector boundary a weight, 0, 1, or 2, equal to the number of cities at its endpoints. Then whenever any subgraph of the graph of sector boundaries and their endpoints has even degree everywhere, it can be used as a boundary between land and water having that subgraph as its coastline. (Again, this is where we use the shape of the planet.) And the total weight of a subgraph equals twice the number of cities that it places on the coast. So there is a solution if and only if there is an even-degree subgraph with total weight equal to twice the number of cities.

But now we’re almost done. The maximum weight even-degree subgraph of any non-negatively-weighted graph is complementary to the minimum weight subgraph that has odd degree at all odd vertices. And this minimum odd subgraph is (with some care about zero-weight edges) the edge-disjoint union of a collection of paths that can be found by a different matching problem: the minimum weight perfect matching, in a complete graph whose vertices are the odd vertices of the input and whose edges are weighted by shortest path distance.

My new preprint “Reconfiguration of Satisfying Assignments and Subset Sums: Easy to Find, Hard to Connect” (arXiv:1805.04055, to appear in COCOON 2018, with Jean Cardinal, Erik Demaine, Bob Hearn, and Andrew Winslow) takes this question a step further, and looks at the connectivity of the solution space of the problem. If you can find a single solution with all cities on the coast, can you get from there to every other solution, by a sequence of steps in which you change the land-water state of a single sector at a time? Can you get from one particular solution to another by the same sorts of steps? The answer is not always yes: the map shown above has six solutions, the six ways of choosing two sectors to be wet and two to be dry. But you can’t get from one to another by changing a single sector, because that would leave you with three wet and one dry or three dry and one wet, flooding or landlocking one of the cities.

It turns out to be PSPACE-hard to tell whether the solution space is connected, or whether a pair of solutions are connected to each other. The map of the figure forms one of the important gadgets in the proof, a truth-setting device, because of its property of having only isolated solutions in its solution space. (In the paper it is drawn more like the graph of a cube, because we draw both the sectors and the cities as vertices in a graph). The preprint also contains additional examples of this phenomenon of a problem in which it is easy to find a single solution but hard to find a connection between solutions. As well as planar monotone nae-3sat (or the planet building problem), they include the subset sum problem (with integers of polynomial magnitude) and the problem of getting from vertex to vertex in a polytope formed by making a constant number of slices to a hypercube.