Really hard problems—Intractability
Intractability
Are there problems that are too hard even for computers? Yes. We will see in Activity 20 that just having a conversation—chatting—is something computers can't do, not because they can't speak but because they can't understand or think of sensible things to say, but that’s not the kind of hard problem we’re talking about here  it's not that computers can’t have conversations, more that we don't know just how we do it ourselves and so we can't tell the computer what to do. But in this section we're going to look at problems where it's easy to tell the computer what to do—by writing a program—but the computer can't do what we want because it takes far too long: millions of centuries, perhaps. Not much good buying a faster computer: if it were a hundred times faster it would still take millions of years; even one a million times faster would take hundreds of years. That's what you call a hard problem—one where it takes far longer than the lifetime of the fastest computer imaginable to come up with a solution!
The activities in Part II on algorithms showed you how to find ways of making computer programs run more efficiently. In this section we look at problems for which no efficient solutions are known, problems that take computers millions of centuries to solve. And we will encounter what is surely the greatest mystery in computer science today: that noone knows whether there's a more efficient way of solving these problems! It may be just that noone has come up with a good way yet, or it may be that there is no good way. We don't know which. And that's not all. There are thousands of problems that, although they look completely different, are equivalent in the sense that if an efficient method is found to solve one, it can be converted into an efficient method to solve them all. In these activities you will learn about these problems.
For teachers
There are three activities in this section. The first involves coloring maps and counting how many colors are needed to make neighboring countries different. The second requires the ability to use a simple street map, and involves placing icecream vans at street corners so that nobody has to go too far to get an icecream. The third is an outdoor activity that uses string and pegs to explore how to make short networks connecting a set of points.
The activities provide a handson appreciation of the idea of complexity—how problems that are very simple to state can turn out to be incredibly hard to solve. And these problems are not abstruse. They are practical questions that arise in everyday activities such as mapping, school timetabling, and road building. The computational underpinning rests on a notion called “NPcompleteness” that is explained in the What's it all about? sections at the end of each activity. Although the activities themselves can be tackled in any order, these sections are intended to be read in the order in which they appear. By the time you reach the end you will have a firm grip on the most important open question in contemporary computer science.
The technical name for this part is “intractability” because problems that are hard to solve are called intractable. The word comes the Latin tractare meaning to draw or drag, leading to the modern usage of tractable as easy to handle, pliant, or docile. Intractable problems are ones that are not easily dealt with because it would take too long to come up with an answer. Although it may sound esoteric, intractability is of great practical interest because a breakthrough in this area would have major ramifications for many different lines of research. For example, most cryptographic codes rely on the intractability of some problems, and a criminal who managed to come up with an efficient solution could have a field day decoding secrets and selling them, or—more simply—just making phoney bank transactions. We will look at these things in Part V—Cryptography.
Activity 13
The poor cartographer—Graph coloring
Summary
Many optimization problems involve situations where certain events cannot occur at the same time, or where certain members of a set of objects cannot be adjacent. For example, anyone who has tried to timetable classes or meetings will have encountered the problem of satisfying the constraints on all the people involved. Many of these difficulties are crystallized in the map coloring problem, in which colors must be chosen for countries on a map in a way that makes bordering countries different colors. This activity is about that problem.
Curriculum Links

Mathematics: Number Level 2 and up. Exploring numbers in other bases. Representing numbers in base two.

Mathematics: Algebra Level 2 and up. Continue a sequential pattern, and describe a rule for this pattern. Patterns and relationships in powers of two.
Skills

Problem solving.

Logical reasoning.

Algorithmic procedures and complexity.

Communication of insights.
Ages
Materials

a whiteboard or similar writing surface.
Each student will need:

a copy of one or more of the worksheets,

movable small colored markers (e.g. counters or poker chips), and

four crayons of different colors (or colored pencils, felt tips etc.)
G
raph Coloring
Introduction
This activity revolves around a story in which the students have been asked to help out a cartographer, or mapmaker, who is coloring in the countries on a map. It doesn't matter which color a country is, so long as it’s different to all bordering countries.
For example, this map shows four countries. If we color Northland red, then Westland and Eastland cannot be red, since their border with Northland would be hard to see. We could color Westland green, and it is also acceptable to color Eastland green because it does not share a border with Westland. (If two countries meet only at a single point, they do not count as sharing a border and hence can be made the same color.) Southland can be colored red, and we end up needing only two colors for the map.
In our story, the cartographer is poor and can't afford many crayons, so the idea is to use as few colors as possible.
Discussion
Describe the problem that the students will be working on, demonstrating the coloring process on a blackboard.
Give out a copy of the first worksheet. This map can be colored correctly using only two colors. Although restricting the number of colors to just two might sound particularly challenging, the task is quite simple compared with maps that require more colors because there is very little choice about what color each country can be.
Have the students try to color the map in with only two colors. In the process they may discover the “hastobe” rule: once one country is colored in, any bordering country has to be the opposite color. This rule is applied repeatedly until all countries are colored in. It is best if the students can discover this rule for themselves, rather than being told it, as it will give them a better insight into the process.
As students complete each exercise they can be given the next sheet to try.
The students may also discover that it is better to use placeholders, such as colored counters, instead of coloring the countries straight away, since this makes it easier for them to change their mind.
For older students, ask them to explain how they know that they have found the minimum number of colors. For example, at least three colors are required for this map because it includes a group of three countries (the largest three), each of which has borders with the other two.
If a student finishes all the sheets early, ask them to try to devise a map that requires five different colors. It has been proved that any map can be colored with only four colors, so this task will keep them occupied for some time! In our experience students will quickly find maps that they believe require five colors, but of course it is always possible to find a fourcolor solution to their maps.
Worksheet Activity: Graph Coloring 1
Color in the countries on this map with as few colors as possible, but make sure that no two bordering countries are the same color.
Worksheet Activity: Graph Coloring 2
Color in the countries on this map with as few colors as possible, but make sure that no two bordering countries are the same color.
Worksheet Activity: Graph Coloring 3
Color in the countries on this map with as few colors as possible, but make sure that no two bordering countries are the same color.
Worksheet Activity: Graph Coloring 4
Color in the countries on this map with as few colors as possible, but make sure that no two bordering countries are the same color.
Variations and Extensions
There is a simple way to construct maps that require only two colors, as shown here. This map was drawn by overlaying closed curves (lines whose beginning joins up with their end). You can draw any number of these curves, of any shape, on top of each other, and you will always end up with a map that can be colored with two colors. Students can experiment with creating this type of map.
Four colors are always enough to color a map drawn on a sheet of paper or on a sphere (that is, a globe). One might wonder (as scientists are paid to do) how many colors are needed for maps drawn on weirder surfaces, such as the torus (the shape of a donut). In this case, one might need five colors, and five is always enough. Students might like to experiment with this.
There are many other entertaining variations on the mapcoloring problem that lead off into directions where much is currently unknown. For example, if I am coloring a map on a sheet of paper by myself, then I know that if I work cleverly, four colors will be enough. But suppose that instead of working alone I am working with an incompetent (or even adversarial) partner, and we take turns at choosing the color for countries. Assume that I work cleverly, while my partner only works “legally” as we take turns coloring countries on the map. How many crayons need to be on the table in order for me in my cleverness to be able to make up for my partner's legal but not very bright (or even subversive) moves? The maximum number isn’t known! In 1992 it was proved that 33 crayons will always be enough, and in 2008 this was improved by a proof that 17 would be sufficient, but we still don't know that this many is ever actually required. (Experts conjecture that fewer than 10 colors are sufficient.) Students might enjoy acting out this situation, which can be played as a twoperson game where you try to maximise the number of colours that your opponent needs.
In another variation of map coloring know as empire coloring, we start with two different maps on two sheets of paper having the same number of countries. Each country on one of the maps (say, the Earth) is paired with exactly one country on the other map (which might be colonies on the Moon). In addition to the usual coloring requirement of different colors for countries that share a border (for both maps) we add the requirement that each Earth country must be colored the same as its colony on the Moon. How many colors do we need for this problem? The answer is currently unknown.
What’s it all about?
The map coloring problem that we have explored in this activity is essentially to find the minimum number of colors—two, three, or four—that are necessary to color a particular map. The conjecture that any map can be colored using only four colors was formulated in 1852, but it was not proved until 1976. Computer science is full of unsolved problems, and knowing that the fourcolor theorem was proved after more than 120 years of attention from researchers is an encouragement to those working on other problems whose solution has eluded them for decades.
Map coloring belongs to a general class of problems known as “graph coloring.” In computer science, a graph is an abstract representation of relationships, as shown here.
As mentioned in Activity 9 on the Muddy City, the term graph is used in a different sense in mathematics to mean a chart displaying numerical data, such as a bar graph, but the graphs that computer scientists use are not related to these. In computer science, graphs are drawn using circles or large dots, technically called “nodes,” to denote objects, with lines between them to indicate some sort of relationship between the objects. The above graph happens to represent the map at the beginning of this activity. The nodes represent the countries, and a line between two nodes indicates that those two countries share a common border. On the graph, the coloring rule is that no connected nodes should be allocated the same color. Unlike a map, there is no limit to the number of colors that a general graph may require, because many different constraints may be drawn in as connecting lines, whereas the twodimensional nature of maps restricts the possible arrangements. The “graph coloring problem” is to find the minimum number of colors that are needed for a particular graph.
In the graph on the right the nodes correspond to subjects in a school. A line between two subjects indicates that at least one student is taking both subjects, and so they should not be timetabled for the same period. Using this representation, the problem of finding a workable timetable using the minimum number of periods is equivalent to the coloring problem, where the different colors correspond to different periods. Graph coloring algorithms are of great interest in computer science, and are used for many realworld problems, although they are probably never used to color in maps!—our poor cartographer is just a fiction.
There are literally thousands of other problems based on graphs. Some are described elsewhere in this book, such as the minimal spanning tree of Activity 9 and the dominating sets of Activity 14. Graphs are a very general way of representing data and can be used to represent all sorts of situations, such as a map made up of roads and intersections, connections between atoms in a molecule, paths that messages can take through a computer network, connections between components on a printed circuit board, and relationships between the tasks required to carry out a large project. For this reason, problems involving graph representations have long fascinated computer scientists.
Many of these problems are very difficult—not difficult conceptually, but difficult because they take a long time to solve. For example, to determine the most efficient solution for a graph coloring problem of moderate size—such as finding the best way to timetable a school with thirty teachers and 800 students—could take years, even centuries, for a computer using the best known algorithm. The problem would be irrelevant by the time the solution was found—and that’s assuming the computer doesn't break down or wear out before it finishes! Such problems are only solved in practice because we are content to work with suboptimal, but still very good, solutions. If we were to insist on being able to guarantee that the solution found was the very best one, the problem would be completely intractable.
The amount of computer time needed to solve coloring problems increases exponentially with the size of the graph. Consider the map coloring problem. It can be solved by trying out all possible ways to color the map. We know that at most four colors are required, so we need to evaluate every combination of assigning the four colors to the countries. If there are n countries, there are 4^{n} combinations. This number grows very rapidly: every country that is added multiplies the number of combinations by four, and hence quadruples the solution time. Even if a computer were invented that could solve the problem for, say, fifty countries in just one hour, adding one more country would require four hours, and we would only need to add ten more countries to make the computer take over a year to find the solution. This kind of problem won't go away just because we keep inventing faster and faster computers!
Graph coloring is a good example of a problem whose solution time grows exponentially. For very simple instances of the problem, such as the small maps used in this activity, it is quite easy to find the optimal solution, but as soon as the number of countries increases beyond about ten, the problem becomes very difficult to do by hand, and with a hundred or more countries, even a computer can take many years to try out all the possible ways of coloring the map in order to choose the optimal one.
Many reallife problems are like this, but must be solved anyway. Computer scientists use methods that give good, but not perfect, answers. These heuristic techniques are often very close to optimal, very fast to compute, and give answers that are close enough for all practical purposes. Schools can tolerate using one more classroom than would be needed if the timetable were perfect, and perhaps the poor cartographer could afford an extra color even though it is not strictly necessary.
Noone has proved that there isn't an efficient way to solve this sort of problem on conventional computers, but neither has anyone proved that there is, and computer scientists are sceptical that an efficient method will ever be found. We will learn more about this kind of problem in the next two activities.
Further reading
Harel discusses the fourcolor theorem, including its history, in Algorithmics. More aspects of the mapcoloring problem are discussed in This is MEGAMathematics! by Casey and Fellows. Kubale’s 2004 book, Graph Colorings, includes a history of the problem. There are many websites that cover this topic.
Solutions and hints
This is the only possible solution for the map on worksheet 1 (of course, the choice of colors is up to the student, but only two different colors are required).
The map at the top of worksheet 2 can be colored correctly using three colors, while the one at the bottom requires four. Here are two possible solutions.
The map on worksheet 3 is a simpler threecolor map, with a possible solution shown here.
Solution for worksheet 4 using just two colors (shaded and white).
Activity 14
Tourist town—Dominating sets
Summary
Many reallife situations can be abstracted into the form of a network or “graph” of the kind used for coloring in Activity 13. Networks present many opportunities for the development of algorithms that are practically useful. In this activity, we want to mark some of the junctions, or “nodes,” in such a way that all other nodes are at most one step away from one of the marked ones. The question is, how few marked nodes can we get away with? This turns out to be a surprisingly difficult problem.
Curriculum Links

Mathematics Level 2: Position and orientation
Skills

Maps.

Relationships.

Puzzle solving.

Iterative goal seeking.
Ages
Materials
Each group of students will need:

a copy of the blackline master Ice Cream Vans, and

several counters or poker chips of two different colors.
You will need

an projector image of the blackline master Ice Cream Vans Solution on a whiteboard, or a whiteboard to draw it on.
D
ominating Sets
Introduction
The Ice Cream Vans worksheet shows a map of Tourist Town. The lines are streets and the dots are street corners. The town lies in a very hot country, and in the summer season icecream vans park at street corners and sell icecreams to tourists. We want to place the vans so that anyone can reach one by walking to the end of their street and then at most one block further. (It may be easier to imagine people living at the intersections rather than along the streets; then they must be able to get icecream by walking at most one block.) The question is, how many vans are needed and on which intersections should they be placed?
Discussion

Divide the students into small groups, give each group the Tourist Town map and some counters, and explain the story.

Show the students how to place a counter on an intersection to mark an icecream van, and then place counters of another color on the intersections one street away. People living at those intersections (or along the streets that come into them) are served by this icecream van.

Have the students experiment with different positions for the vans. As they find configurations that serve all houses, remind them that vans are expensive and the idea is to have as few of them as possible. It is obvious that the conditions can be met if there are enough vans to place on all intersections—the interesting question is how f
ew you can get away with.

The minimum number of vans for Tourist Town is six, and a solution is shown here. But it is very difficult to find this solution! After some time, tell the class that six vans suffice and challenge them to find a way to place them. This is still quite a hard problem: many groups will eventually give up. Even a solution using eight or nine vans can be difficult to find.

The map of Tourist Town was made by starting with the six map pieces at the bottom of the Ice Cream Vans solution worksheet, each of which obviously requires only one icecream van, and connecting them together with lots of streets to disguise the solution. The main thing is not to put any links between the solution intersections (the open dots), but only between the extra ones (the solid dots). Show the class this technique on the board or using a projector.

Get the students to make their own difficult maps using this strategy. They may wish to try them on their friends and parents–they will find that they can create puzzles that they can solve but others can’t! These are examples of what is called a “oneway function”: it's easy to come up with a puzzle that is very difficult to solve—unless you’re the one who created it in the first place. Oneway functions play a crucial role in cryptography (see Activities 17 and 18).
Worksheet Activity: Ice Cream Vans
Work out how to place icecream vans on the street intersections so that every other intersection is connected to one that has a van on it.
Worksheet Activity: Ice Cream Vans Solution
Display this to the class to show how the puzzle was constructed.
Variations and extensions
There are all sorts of situations in which one might be faced with this kind of problem in town planning: locating mailboxes, wells, firestations, and so on. And in real life, the map won’t be based on a trick that makes it easy to solve. If you really have to solve a problem like this, how would you do it?
There is a very straightforward way: consider all possible ways of placing icecream vans and check them to see which is best. With the 26 street corners in Tourist Town, there are 26 ways of placing one van. It's easy to check all 26 possibilities, and it’s obvious that none of them satisfies the desired condition. With two vans, there are 26 places to put the first, and, whichever one is chosen for the first, there are 25 places left to put the second (obviously you wouldn’t put both vans at the same intersection): 26 × 25 = 650 possibilities to check. Again, each check is easy, although it would be very tedious to do them all. Actually, you only need to check half of them (325), since it doesn’t matter which van is which: if you’ve checked van 1 at intersection A and van 2 at intersection B then there’s no need to check van 1 at B and van 2 at A. You could carry on checking three vans (2600 possibilities), four vans (14950 possibilities), and so on. Clearly, 26 vans are enough since there are only 26 intersections and there’s no point in having more than one van at the same place. Another way of assessing the number of possibilities is to consider the total number of configurations with 26 intersections and any number of vans. Since there are two possibilities for each street corner—it may or may not have a van—the number of configurations is 2^{26}, which is 67,108,864.
This way of solving the problem is called a “bruteforce” algorithm, and it takes a long time. It’s a widely held misconception that computers are so fast they can solve just about any problem quickly, no matter how much work it involves. But that’s not true. Just how long the bruteforce algorithm takes depends on how quick it is to check whether a particular configuration is a solution. To check this involves testing every intersection to find the distance of the nearest van. Suppose that an entire configuration can be tested in one second. How long does it take to test all 2^{26} possibilities for Tourist Town? (Answer: 2^{26} is about 67 million; there are 86,400 seconds in a day, so 2^{26} seconds is about 777 days, or around two years.) And suppose that instead of one second, it took just one thousandth of a second to check each particular configuration. Then the same two years would allow the computer to solve a 36intersection town, because 2^{36} is about 1000 times 2^{26}. Even if the computer was a million times faster, so that one million configurations could be checked every second, then it would take two years to work on a 46intersection town. And these are not very big towns! (How many intersections are there in your town?)
Since the bruteforce algorithm is so slow, are there other ways to solve the problem? Well, we could try the greedy approach that was so successful in the muddy city (Activity 9). We need to think how to be greedy with icecreams—I mean how to apply the greedy approach to the icecream van problem. The way to do it is by placing the first van at the intersection that connects the greatest number of streets, the second one at the next most connected intersection, and so on. However, this doesn’t necessarily produce a minimum set of icecream van positions—in fact, the most highly connected intersection in Tourist Town, which has five streets, isn’t a good place to put a van (check this with the class).
Let’s look at an easier problem. Instead of being asked to find a minimum configuration, suppose you were given a configuration and asked whether it was minimal or not. In some cases, this is easy. For example, this diagram shows a much simpler map whose solution is quite straightforward. If you imagine the streets as edges of a cube, it’s clear that two icecream vans at diagonally opposite cube vertices are sufficient. Moreover, you should be able to convince yourself that it is not possible to solve the problem with fewer than two vans. It is much harder—though not impossible—to convince oneself that Tourist Town cannot be serviced by less than six vans. For general maps it is extremely hard to prove that a certain configuration of icecream vans is a minimal one.
What’s it all about?
One of the interesting things about the icecream problem is that noone knows whether there is an algorithm for finding a minimum set of locations that is significantly faster than the bruteforce method! The time taken by the bruteforce method grows exponentially with the number of intersections—it is called an exponentialtime algorithm. A polynomialtime algorithm is one whose running time grows with the square, or the cube, or the seventeenth power, or any other power, of the number of intersections. A polynomialtime algorithm will always be faster for sufficiently large maps—even (say) a seventeenthpower algorithm—since an exponentiallygrowing function outweighs any polynomiallygrowing one once its argument becomes large enough. (For example, if you work it out, whenever n is bigger than 117 then n^{17} is smaller than 2^{n}). Is there a polynomialtime algorithm for finding the minimum set of locations?—noone knows, although people have tried very hard to find one. And the same is true for the seemingly easier task of checking whether a particular set of locations is minimal: the bruteforce algorithm of trying all possibilities for smaller sets of locations is exponential in the number of intersections, and polynomialtime algorithms have neither been discovered nor proved not to exist.
Does this remind you of map coloring (Activity 13)? It should. The icecream van question, which is officially called the “minimum dominating set” problem, is one of a large number—thousands—of problems for which it is not known whether polynomialtime algorithms exist, in domains ranging from logic, through jigsawlike arrangement problems to map coloring, finding optimal routes on maps, and scheduling processes. Astonishingly, all of these problems have been shown to be equivalent in the sense that if a polynomialtime algorithm is found for one of them, it can be converted into a polynomialtime algorithm for all the others—you might say that they stand or fall together.
These problems are called NPcomplete. NP stands for “nondeterministic polynomial.” This jargon means that the problem could be solved in a reasonable amount of time if you had a computer that could try out an arbitrarily large number of solutions at once (that’s the nondeterministic part). You may think this is a pretty unrealistic assumption, and indeed it is. It’s not possible to build this kind of computer, since it would have to be arbitrarily large! However, the concept of such a machine is important in principle, because it appears that NPcomplete problems cannot be solved in a reasonable amount of time without a nondeterministic computer.
Furthermore, this group of problems is called complete because although the problems seem very different—for example, mapcoloring is very different from placing icecream vans—it turns out that if an efficient way of solving one of them is found, then that method can be adapted to solve any of the problems. That’s what we meant by “standing or falling together.”
There are thousands of NPcomplete problems, and researchers have been attacking them, looking for efficient solutions, for several decades without success. If an efficient solution had been discovered for just one of them, then we would have efficient solutions for them all. For this reason, it is strongly suspected that there is no efficient solution. But proving that the problems necessarily take exponential time is the most outstanding open question in theoretical computer science—possibly in all of mathematics—today.
Further reading
Harel’s book Algorithmics introduces several NPcomplete problems and discusses the question of whether polynomialtime algorithms exist. Dewdney’s Turing Omnibus also discusses NPcompleteness. The standard computer science text on the subject is Garey & Johnson’s Computers and Intractability, which introduces several hundred NPcomplete problems along with techniques for proving NPcompleteness. However, it is fairly heavy going and is really only suitable for the computer science specialist.
Activity 15
Ice roads —Steiner trees
Summary
Sometimes a small, seemingly insignificant, variation in the specification of a problem makes a huge difference in how hard it is to solve. This activity, like the Muddy City problem (Activity 9), is about finding short paths through networks. The difference is that here we are allowed to introduce new points into the network if that reduces the path length. The result is a far more difficult problem that is not related to the Muddy City, but is algorithmically equivalent to the cartographer’s puzzle (Activity 13) and Tourist Town (Activity 14).
Skills

Spatial visualization.

Geometric reasoning.

Algorithmic procedures and complexity.
Ages
Materials
Each group of students will need

five or six pegs to place in the ground (tent pegs are good, although a coat hanger cut into pieces which are then bent over is fine),

several meters of string or elastic,

a ruler or tape measure, and

pen and paper to make notes on.
Ice Roads
Introduction
The previous activity, Tourist Town, took place in a very hot country; this one is just the opposite. In the frozen north of Canada (so the story goes), in the winter on the huge frozen lakes, snowplows make roads to connect up drill sites so that crews can visit each other. Out there in the cold they want to do a minimum of road building, and your job is to figure out where to make the roads. There are no constraints: highways can go anywhere on the snow—the lakes are frozen and covered. It’s all flat.
The roads should obviously travel in straight stretches, since introducing bends would only increase the length unnecessarily. But it’s not as simple as connecting all the sites with straight lines, because adding intersections out in the frozen wastes can sometimes reduce the total road length—and it’s total length that’s important, not travel time from one site to another.
In this figure, (a) shows three drill sites. Connecting one of them to each of the others (as in (b)) would make an acceptable road network. Another possibility is to make an intersection somewhere near the center of the triangle and connect it to the three sites (c). And if you measure the total amount of road that has been cleared, this is indeed a better solution. The extra intersection is called a “Steiner” point after the Swiss mathematician Jacob Steiner (1796–1863), who stated the problem and was the first to notice that the total length can be reduced by introducing new points. You could think of a Steiner point as a new, fictitious, drill site.
Discussion

Describe the problem that the students will be working on. Using the example above, demonstrate to the students that with three sites, adding a new one sometimes improves the solution by reducing the amount of roadbuilding.

The students will be using four points arranged in a square, as illustrated in (a). Go outside and get each group to place four pegs in the grass in a square about 1 meter by 1 meter.

Get the students to experiment with connecting the pegs with string or elastic, measuring and recording the minimum total length required. At this stage they should not use any Steiner points. (The minimum is achieved by connecting three sides of the square, as in (b), and the total length is 3 meters.)

Now see if the students can do better by using one Steiner point. (The best place is in the center of the square, (c). Then the total length is 2√2 = 2.83 meters.) Suggest that they might do even better using two Steiner points. (Indeed they can, by placing the two points as in (d), forming 120 degree angles between the incoming roads. The total length is then 1 + √3 = 2.73 meters.)

Can the students do better with three Steiner points? (No – two points are best, and no advantage is gained by using more.)

Discuss with the students why these problems seem hard. (It’s because you don’t know where to put the Steiner points, and there are lots of possibilities to try out.)
Worksheet Activity: Steiner Tree Example 1
Find a way of linking these drill sites with the shortest possible ice roads.
Worksheet Activity: Steiner Tree Example 2
Find a way of linking these drill sites with the shortest possible ice roads.
Variations and extensions

An interesting experiment for groups that finish the original activity early is to work with a rectangle about 1 meter by 2 meters (a). The students will find that adding one Steiner point makes things worse, but two give an improved solution. (The lengths are 4 meters for (b), 2√5 = 4.47 meters for (c), and 2 + √3 = 3.73 meters for (d).) See if they can figure out why the onepoint configuration does so much worse for rectangles than for squares. (It’s because when the square is stretched into a rectangle, the amount of stretch gets added just once into (b) and (d), but both diagonals increase in (c).)

Minimal Steiner tree for the first example
Older students can work on a larger problem. Two layouts of sites to connect with ice roads are given in the worksheets. They can experiment with different solutions either using new copies of the worksheet, or by writing with removable pen on a transparency over the top of the sheet. Alternatively, the maps can be marked out on the ground using pegs. They can let the class know when they think they’ve set a new record for the shortest distance. (The figures on the right show the minimal solution for the first example and two possible solutions for the second, whose total
Two possible Steiner trees for the second example
length is quite similar.) The fact that there are two such similar solutions illustrates why these kinds of problem are so hard—there are so many choices about where to put the Steiner points!

Ladder networks like this provide another way to extend the problem.
Some minimal Steiner trees for ladder networks are shown here.
The one for a tworung ladder is just the same as for a square. However, for a threerung ladder the solution is quite different—as you will discover if you try to draw it out again from memory! The solution for four rungs is like that for two tworung ladders joined together, whereas for five rungs it is more like an extension of the threerung solution. In general, the shape of the minimal Steiner tree for a ladder depends on whether it has an even or odd number of rungs. If it is even, it is as though several tworung ladders were joined together. Otherwise, it's like a repetition of the threerung solution. But proving these things rigorously is not easy.

Another interesting activity is to construct soapbubble models of Steiner trees. You can do this by taking two sheets of rigid transparent plastic and inserting pins between them to represent the sites to be spanned, as shown here.
Now dip the whole thing into a soap solution. When it comes out, you will find that a film of soap connects the pins in a beautiful Steinertree network.
Unfortunately, however, it isn't necessarily a minimal Steiner tree. The soap film does find a configuration that minimizes the total length, but the minimum is only a local one, not necessarily a global one. There may be completely different ways of placing the Steiner points to give a smaller total length. For example, you can imagine the soap film looking like the first configuration in Extension 2 when it is withdrawn from the liquid on one occasion, and the second configuration on another.
What’s it all about?
The networks that we’ve been working on are minimal Steiner trees. They’re called “trees” because they have no cycles, just as the branches on a real tree grow apart but do not (normally) rejoin and grow together again. They’re called “Steiner” trees because new points, Steiner points, can be added to the original sites that the trees connect. And they’re called “minimal” because they have the shortest length of any tree connecting those sites. In the Muddy City (Activity 9) we learned that a network connecting a number of sites that minimizes the total length is called a minimal spanning tree: Steiner trees are just the same except that new points can be introduced.
It’s interesting that while there is a very efficient algorithm for finding minimal spanning trees (Activity 14)—a greedy one that works by repeatedly connecting the two closest sofarunconnected points—there is no general efficient solution to the minimal Steiner problem. Steiner trees are much harder because you have to decide where to put the extra points. In fact, rather surprisingly, the difficult part of the Steiner tree problem is not in determining the precise location of the Steiner points, but in deciding roughly where to put them: the difference between the two solutions to Example 2, for example. Once you know what regions to put the new points in, finetuning them to the optimum position is relatively simple. Soap films do that very effectively, and so can computers.
Finding minimal Steiner trees is part of a story that involved saving big money in the telephone business. Before 1967, when corporate customers in the US operated large private telephone networks, they leased the lines from a telephone company. The amount they are billed is not calculated on the basis of how the wires are actually used, but on the basis of the shortest network that would suffice. The reasoning is that the customer shouldn’t have to pay extra just because the telephone company uses a roundabout route. Originally, the algorithm that calculated how much to charge worked by determining the minimal spanning tree. However, around 1967 it was noticed by a customer—an airline, in fact, with three major hubs—that if they requested a fourth hub at an intermediate point then the total length of the network would be reduced. The telephone company was forced to reduce charges to what they would have been if there was a telephone exchange at the Steiner point! Although, for typical configurations, the minimal Steiner tree is only 5% or 10% shorter than the minimal spanning tree, this can be a worthwhile saving when large amounts of money are involved. The Steiner tree problem is sometimes called the “shortest network problem” because it involves finding the shortest network that connects a set of sites.
If you have tackled the two preceding activities, the cartographer’s puzzle and tourist town, you will not be surprised to hear that the minimal Steiner tree problem is NPcomplete. As the number of sites increases, so does the number of possible locations for Steiner points, and trying all possibilities involves an exponentiallygrowing search. This is another of the thousands of problems for which it simply isn’t known whether exponential search is the best that can be done, or whether there is an asyetundiscovered polynomialtime algorithm. What is known, however, is that if a polynomialtime algorithm is found for this problem, it can be turned into a polynomialtime algorithm for graph coloring, for finding minimal dominating sets—and for all the other problems in the NPcomplete class.
We explained at the end of the previous activity that the “NP” in NPcomplete stands for “nondeterministic polynomial,” and “complete” refers to the fact that if a polynomialtime algorithm is found for one of the NPcomplete problems it can be turned into polynomialtime algorithms for all the others. The set of problems that are solvable in polynomial time is called P. So the crucial question is, do polynomialtime algorithms exist for NPcomplete problems—in other words, is P = NP? The answer to this question is not known, and it is one of the great mysteries of modern computer science.
Problems for which polynomialtime algorithms exist—even though these algorithms might be quite slow—are called “tractable.” Problems for which they do not are called “intractable,” because no matter how fast your computer, or how many computers you use together, a small increase in problem size will mean that they can’t possibly be solved in practice. It is not known whether the NPcomplete problems—which include the cartographer’s puzzle, tourist town, and ice roads—are tractable or not. But most computer scientists are pessimistic that a polynomialtime algorithm for NPcomplete problems will ever be found, and so proving that a problem is NPcomplete is regarded as strong evidence that the problem is inherently intractable.



“I can't find an efficient algorithm, I guess I'm just too dumb.”

“I can't find an efficient algorithm, because no such algorithm is possible.”

“I can't find an efficient algorithm, but neither can all these famous people.”

What to do when you can't find an efficient algorithm: three possibilities
What can you do when your boss asks you to devise an efficient algorithm that comes up with the optimal solution to a problem, and you can’t find one?—as surely happened when the airline hit upon the fact that network costs could be reduced by introducing Steiner points. If you could prove that there isn’t an efficient algorithm to come up with the optimal solution, that would be great. But it’s very difficult to prove negative results like this in computer science, for who knows what clever programmer might come along in the future and hit upon an obscure trick that solves the problem. So, unfortunately, you’re unlikely to be in a position to say categorically that no efficient algorithm is possible—that the problem is intractable. But if you can show that your problem is NPcomplete, then it’s actually true that thousands of people in research laboratories have worked on problems that really are equivalent to yours, and also failed to come up with an efficient solution. That may not get you a bonus, but it’ll get you off the hook!
Of course, in real life these problems still need to be solved, and in that case people turn to heuristics – algorithms that don’t guarantee to give the best possible solution, but do give a solution within a very small percentage of the optimal. Heuristic algorithms can be very fast, and the wastage of not finding the best possible solution can be fairly small, so they are good enough to get on with the job. It’s just frustrating to know that there might be a slightly better timetable, or a slightly better layout of a network or roads.
Further reading
The cartoon is from Garey and Johnson's classic book Computers and Intractability.
The “Computer recreations” column of Scientific American, June 1984, contains a brief description of how to make Steiner trees using soap bubbles, along with interesting descriptions of other analog gadgets for problem solving, including a spaghetti computer for sorting, a cat's cradle of strings for finding shortest paths in a graph, and a lightandmirrors device for telling whether or not a number is prime. These also appear in a section about analog computers in Dewdney's Turing Omnibus.
Part V
Share with your friends: