Problems reducing to a graph-theory algorithm

Question

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!

Answer 1

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)

Answer 2

I expected a flood of responses to this question, since there are so many lovely examples. That flood does not seem to have materialised yet, so let me add an old classic. I hope it isn’t too famous to be worth mentioning, and that adding it as a separate answer is the correct protocol.

I’m thinking of Steve Fisk’s celebrated proof of the Art Gallery theorem, which is in the form of an algorithm.

We are given the floor plan of an art gallery as a simple polygon in the plane with $n$ vertices, and we wish to place some (motionless point) guards into the polygon so that the whole of the interior of the polygon is visible to at least one guard.

We can see that we may need as many as $\lfloor\frac n3\rfloor$ guards by considering comb-shaped polygons with $n=3k$ vertices:

(There must be a guard in each of the grey triangles, and there are $k$ disjoint such triangles, so we need at least $k=\frac n3$ guards.)

The problem, then, is to place no more than $\lfloor\frac n3\rfloor$ guards into a simple polygon with $n$ vertices in such a way that one of the guards can see any point in the interior of the polygon.

Fisk’s algorithm is as follows: triangulate the polygon to obtain a planar graph whose vertices are the vertices of the original polygon and whose faces are triangles, and then three-colour the vertices so each face has a vertex of each colour. At least one of the three colours occurs $\leq\lfloor\frac n3\rfloor$ times: position guards at the vertices that are painted this colour. Since each triangle has a guard at one of its vertices, and a triangle is entirely visible from any one of its vertices, the whole of the polygon must be visible to at least one guard.

Thus a difficult-sounding purely geometric problem is solved by three-colouring the vertices of a planar graph.

---

I should perhaps note that prolific MO contributor Joseph O’Rourke literally wrote the book on art gallery theorems and algorithms.

Answer 3

The OP contains the specifications

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.

The following is about as trivial as can be (even in a technical sense of 'trivial': it is based on what is sometimes presented in introductory graph theory lectures as the 'First Theorem of Graph Theory'), but it fits each of the three specifications above:

To find the number of undirected connections in a finite network of which you only have knowledge in the form of a photograph. $\hspace{150pt}$(problem)

That is: imagine a situation in which a programmer faces the task of programming a camera-equipped machine to 'look' at such a photograph and correctly output the total number of connections.

To make the problem-description consistent with the 'worked example' below, imagine the company running the search engine which kindly ran for me a Gilbert--Erdős–Rényi-random graph simulation, decides to *empirically test that the number of connection shown on the screen of users equals the number of connections that the search engine returns as a numeral when asked to do so. For the sake of argument, suppose that the company will have none of 'formal verification' of code (though I think this would give greater security) but has resolved to test this very very empirically, by filming a screen. To reach usefully large sample sizes, they will have to teach a camera-equipped machine how to count the lines.

Among the "first, naive algorithms that spring to mind to solve this (finite) problem" (to quote the OP) is an "awkward" one: to rasterize the picture, to systematically scan it, to code-up some recognition-of-elongated-shapes, to keep track of what elongated shape you already have counted, to finally somehow arrive at an estimate of the number of connections. (Also note: this approach does not involve any necessary check of correctness, however weak, unlike the approach I am proposing; see the remark at the very end.)

I think that, especially if the photograph is messy, the input data to the machine "[does] not immediately involve graph theory,".

Now comes the "little translation, into a common problem in graph theory", namely into what is arguably the most trivial of all graph theoretic problems:

to find the number of edges of a specified graph.

And this problem ("aha!" goes the mathematician, while the programmer heaves the required "sigh of relief") reduces to simply 'doing a sum' of natural numbers (plus a little pattern recognition, though not a recognition of elongated/curvilinear shapes anymore): the problem reduces to summing the degree sequence of the relevant graph. (The reason is what is whimsically called 'The Handshaking Lemma', or a little presumptiously called 'The First Theorem of Graph heory'¹)

More precisely, we idealize (and what an important, mathematical activity this is: idealizing sense-data) the situation, by imagining that there is an abstract graph.

Now we know what to teach the machine:

(0) identify all 'vertex-like' points of the photograph,

(1) 'cookie-cutter' a small circle-shaped portion around each such 'point',

(2) forget the vast majority of the 'photograph',

(3) collect the 'cookies' (the order and position of the 'cookies' is irrelevant, any data-structure which keeps the set of the 'cookies' will be serviceable),

(4) now solve a much easier patter-recognition-problem, on each of the 'cookies': to recognize the number of 'rays' in the 'star-like' shapes (there will be noise, yet I am confident that this task can be routinely done, reliably, by methods of Computational Homology, methods which were more-or-less made for doing precisely this: extracting meaningful integer-valued invariants from noisy black-and-white-pictures. If not, I am confident that this task will be routine for people working in machine-learning/pattern-recognition.)

To summarize: where was the graph-theory here?

On "the surface", a messy photograph of a tangle of connections in a network does not look like a graph. At the very least, I am sure that a person not knowing concepts of graph theory would, when having to teach a machine what to do with the sense-data fed to it, be more likely to code-up a 'rasterize-and-scan-the-whole-picture-and-invent-heuristics-to-recognize' approach than taking the graph-theoretically-informed 'cookie-cutter' approach.

Worked Example. Let the given 'photograph' be the network-like part of the following photograph, taken from the webpage of a known search-engine, with the 'order' given to the engine shown in the first line of the image:

Insert now a "haha!" and "sigh of relief". No pattern-recognition of 'line-like' shapes is necessary; it suffices to identify the 'vertex-like' parts of the image, and then do the following:

First the 'cookie-cutting' (here, I use counterclockwise ordering):

Now follows a conversion of the 'gray-scale cookies' to something combinatorial (essentially: (0,1)-matrices, given as a black-and-white rid). The diaphanous blue regions do not carry any information; they associate each gray-scale 'observation' with the corresponding (0,1)-matrix, yet this association could be done by the mind of the observer unaided by the blue regions, for the correspondence is quite uniquely determined.

These '0-1-matrices' weren't 'made-up': I had the 'GIMP' software compute it for me, via the "Indexed Color Conversion" functionality, with the option "Use black and white (1-bit) palette" and with "Color-dithering: Floyd-Steinberg (normal)" turned on. What I give here should even be quite a 'reproducible experiment'. It should be possible to have a machine produce the same '0-1-matrices' from the gray-scale pictures.

Now insert here some expert advice of someone more versed in computational homology (or some other suitable method: something via eigenvalues of the black-and-white matrices perhaps (though these eigenvalues will not be real-valued? using some appropriate heat-flow?); or someone more versed in machine-learning/pattern-recognition algorithms²) than the writer of these lines (who only had to learn computational homology for an exam a few years ago, yet does not work with it), telling us which "Sooo much time"-saving out-of-the-box routine we should use to count the number of 'rays' in the 'star-shaped' matrix-pictures, and now the following numbers come pouring forth:

3 2 6 5 3 4 4 5 7 4 1

Now the so-called First Theorem of Graph Theory completes the "reducing" of the problem to a "graph theory algorithm": it remains to calculate

$\frac12\cdot (3 + 2 + 6 + 5 + 3 + 4 + 4 + 5 + 7 + 4 + 1) = \frac12\cdot 44 = 22$

to know (by the 'First Theorem of Graph Theory') that this is the number of edges(=connections) in the 'photograph' of the random graph.

This was a reduction, of sorts.

On which side of your "fine line" this is, I cannot know in advance. By the way, I agree with Dirk Liebhold's comment, that this is very context-dependent question, any answer will be 'tainted' by context.

Addition. Another small contribution of graph theory in solving this problem:

If the above sum (in the example it was 44) does not come out even, then something somewhere must have gone wrong.

In that sense, the 'First Theorem of Graph Theory' also give a very weak 'check'/'necessary condition' for the correct execution of the algorithm. One of course is not told by the criterion where and why an error has occurred, only that somewhere something has gone wrong. Also, if the sum comes out even, this, needless to say, does not imply that it is the correct one.

¹ _{Incidentally, this commonly encountered designation is not only a little presumptious, but also technically-wrong if very strictly construed: in the strictest sense, 'Graph Theory' is the theory, in the model-theoretic sense, of the class of irreflexive symmetric relations on a set, and, as such, has a one-element signature consisting of a single binary relation symbol. The so-called 'First Theorem of Graph Theory', though, uses a larger signature: which exactly, depends on your formalization, but you can argue that it uses the signature $(\sim,\mathrm{deg},+,\Sigma,\lVert\cdot \rVert)$, where $\sim$ is the binary relation symbol, and $\mathrm{deg}$ and $\lVert\cdot\rVert$ are unary function symbols, the intended interpretation of the former being the degree of its argument, the one of the latter being the number of edges of its argument.}

² _{It would be a nice example of focused interdisciplinary work if someone who knows more about pattern recognitino would leave a relevant comment on what is considered the best method to count the number of 'rays' in the 'star-shaped' '0-1-matrices'. One can for example first 'blow-up' each pixel until the 0-th Betti number (=number of connected components) has become equal to 1, upone which, in a sense, the 'noise' is 'gone', and then one has to come up with a functorial method to 'count the number of bumps along the perimeter'. Ideally, the present answer would in the end feature a completely 'synthetic' method of counting the number of connection in a 'photograph' of a 'network', that is, by 'putting together' existing concepts.}