Introduction

Okay, the title is bit misleading. Playing minesweaper is not actually NP-complete, but a very similar problem is. Remember that for something to be a NP-complete problem we have to have a language (just a fancy set) and ask a yes/no question whether something is in it or not.

So given an undirected graph where some nodes are labeled with integers we can ask whether we can place mines on unlabeled nodes so that the labels are accurate Minesweeper hints. To be precise, we want each label node to have exactly as much mined neighbours as its label says.

This question is a problem in Michael Sipser's Introduction to the Theory of Computation and I thank him for the fun time I had thinking about it.

Notation

We will call this language of valid Minesweeper-labeled graphs \(Mine\).

\(Mine \in NP\)

I will only sketch this part as it is usually the easiest bit in an NP-complete proof.

So the idea is that we can easily build an polynomial time verifier. It takes a Minesweeper-labeled graph and a set of nodes that should be mined as input. We can then easily check if a given node has the right number of neighbouring mines. In that way we can verify that a given graph has a valid mining.

It is obvious that such a certificate (the set of nodes that should have mines) can only ever exist if there is a legal way to place mines; the certificate is the placement of the mines.

That the certificate can actually be encoded polynomial in the length of the graph and that the verifier actually runs in poly-time is left as an exercise to the reader.

\(Mine\) is NP-hard

I will do this by giving a polynomial time reduction of the independent set problem (which we write \(IS\)) to \(Mine\). That means we prove that any algorithm that can solve \(Mine\) in poly-time gives rise to an algorithm that solves \(IS\) in poly-time. In that sense we can say \(Mine\) is at least as hard as \(IS\) and we know that \(IS\) is really hard, i.e. in \(NPC\).

Theorem: \(IS \le_p Mine\)

Proof. Let \((G, k)\) be any question we might ask of \(IS\). That is \(G=(V,E)\) is an undirected graph and we want to know if it has an independent set of size at least \(k\).

We construct a Minesweeper graph \(G'=(V', E')\), by taking taking the objects of \(G\) as vertices. That means every vertex and edge of \(G\) becomes a vertex in \(G'\). We want to force any valid mining to mine exactly the vertices of an independent set of the correct size. Also if there is no independet set of the right size there should be no valid mining.

Let's get started finding such a construction.

The idea is now that we connect each edge-vertex to the two vertex-vertices it's adjacent to in \(G\). We then label this edge-vertex with 1. That means that at most one of the adjacent vertices can be mined. We then add a new vertex \(v_{\text{center}}\) and label it with \(k\). This vertex is connected to every vertex-vertex. We now force that exactly \(k\) vertices must be mined.

Only one problem remains: What if we don't want to mine one of the adjacent vertices to an edge? That would be impossible in our current construction. To solve that problem we introduce an alternative vertex for every edge that can be mined if needed. This vertex is only connected to the one edge-vertex it belongs to.

This construction can obviously be done in polynomial time.

Now that we have described our construction, let's prove it correct.

(\(\rightarrow\)) Assume that \((G,k) \in IS\). We want to show that \(G' \in Mine\). We know that \(G\) hat an set of size at least \(k\). To get an independent set of the correct size we can just leave out any additional vertices. Let call any resulting set \(S \subseteq V\).

We know mine the vertices of \(V'\) that correspond to elements of \(S\) and if any edges remain where no adjacent edge is mined, we mine the corresponding edge-alternative-vertices. We will show that this mining is valid.

We instantly get that \(v_\text{center}\) has exactly \(k\) mined neighbours as required.

Additionally since the set is independent no edge can have both its adjacent edges in \(S\), so no two vertex-vertices neighbouring an edge-vertex have been mined. Because we only mined the edge-alternative-vertices where needed, every edge has exactly one mined neighbour. Therefore all labels are satisfied and the mining is valid.

(\(\leftarrow\)) Let \(G'\) now have a valid mining. We want to show that \(G\) has an independent set of size \(k\). Take any valid mining and let \(S'\) denote the set of mined vertex-vertices. We claim that the set \(S\) of corresponding vertices in \(G\) is an independent set of the right size.

The size is exactly \(k\) because \(v_\text{center}\) needs to have exactly \(k\) mined neighbours in order for a mining to be valid.

To see that the set is independent, assume that it is not. Then we have \(u,v \in S\) such that there is an edge \(u \leftrightarrow v\) in \(G\). Then there is a vertex \(v_{\{u,v\}}\) in \(G'\) that has two mined neighbour. That is the needed contradiction since we labeled every edge-vertex 1. Therefore \(S\) is independent.

This concludes the proof, since we have shown that for every graph-integer tuple \((G, k)\) we can construct a labeled graph \(G'\) in polynomial time such that \((G,k) \in IS \iff G' \in Mine\). ∎

Corollary: \(Mine\) is NP-hard.

Proof. We know that \(IS\) is NP-hard and by our theorem we conclude that \(Mine\) is NP-hard. ∎