This is essentially a question in pedagogy — the answers could be useful to teach (or rather, motivate) graph theory, and especially the algorithmic side of it.
I have been very impressed with this example:
Question: What is the maximum size of a set of integers between 1 and 100 such that for any pair (a,b), the difference a-b is not a square ?
The first, naive algorithms that spring to mind to solve this (finite) problem are awkward. However, let me quote: " This problem can be defined as a Graph problem : we create a vertex for each integer, and link two integers if their difference is a square. We but have to find a maximal independent set in this graph ! "
Using this, a few trivial lines of Sage code give the answer (see the link). Sooo much time is saved for the coder!
Are there more examples like this one?
To be more precise, I'm looking for problems which:
- do not immediately involve graph theory, on the surface,
- reduce, after a little translation, into a common problem in graph theory (find a matching, find a colouring…).
- there should be a "haha!" effect for the mathematician, and a sigh of relief for the programmer.
I heard another nice one in a talk by Tim Gowers. A university wants to organize its exams. Some students take several exams. Some rooms and some time slots are available. Help them. Solution: each exam (maths, physics, etc) is a vertex; place one edge between exams if there is one student taking both; define "colours" to be pairs (room, time). Now you have to colour the graph such that adjacent vertices are in different colours.
There is a fine line between these great examples, and the articifial ones which I find disappointing, such as "$n$ couples having each $k$ children all want to shake hands on different days such that…". In fact, I should add that I'm certain to have a preference for problems involving maths (like the first one above) rather than "real life" (like the second).
Usual precaution: if this is not appropriate for MO, let me know and I will not be offended!
Best Answer
What a great question. I’m sure there will be many lovely examples. Here is one I stumbled on last year which seems to fit.
I saw an online demonstration of a simulated annealing algorithm for the following problem: a digital photograph has been “shredded” by randomly shuffling the columns of pixels, and we wish to recover the original unshredded image. Here is such a shredded photograph.
The simulated annealing algorithm is able to put the photograph back together to some extent by moving similar columns of pixels together, resulting in this:
The moment of enlightenment for me was realising that the problem is one of finding a minimum-weight Hamiltonian path in a weighted complete graph: the vertices of the graph are the columns of pixels, and the edge weights are given by a similarity measure showing how well two columns match. Therefore we can bring to bear all the well-developed algorithmic machinery aimed at the Travelling Salesman Problem. Using Keld Helsgaun’s LKH solver gives an algorithm that is orders of magnitude faster, and is able to reconstruct this particular photograph with not a pixel out of place:
(although it is flipped left-to-right: there is not much we can do about that possibility)
As an amusing coda, if the rows as well as the columns of the image are shuffled then the result looks more like a decorative rug than a photograph of Paris at night:
but the original photograph may still be recovered by running the algorithm twice – once for the rows, and once for the columns – though now the result might be flipped upside-down as well as left-to-right.
Incidentally, the reason I was familiar with TSP-solving technology is that I had used it earlier to disprove a 20-year-old conjecture in combinatorics: another problem that doesn’t sound like graph theory at first blush.
Link to code: GitHub
Photo credit: Blue Hour in Paris, by Falcon® Photography (CC BY-SA)