# Modeling a (rather silly) magnet problem using graphs

I have a magnet kit, which comes with 144 cylindrical magnets (they are actually rings) and 38 balls. Here is a link for those interested: http://www.kjmagnetics.com/proddetail.asp?prod=K7

The balls are not magnets, but the rods to connect them are. I discovered early on the interesting property that the balls tend to "add up" the magnetic poles of the magnets they are attached to. For instance, if a ball has four magnets attached to it, two of them on their south poles and two of them on their north poles, then the magnetic fields tend to "cancel out". If I take one of those magnets and reverse it, however, so that now we have three north poles and one south pole on the ball, all magnets still stick to the ball, but now the ball gains two units of "northness". The ball itself is now able to magnetically attract other balls whereas the neutrally magnetized ball from earlier does not. It's also possible to get a feel for how "magnetized" a ball is by holding a magnet close to it. The magnet will tend to prefer to attach to it with one pole rather than the other if it is "charged". What's interesting as a consequence of all this is that if you have a ball with an odd number of magnets connected to it, it has a net magnetism (of an odd amplitude) and a ball with an even number of magnets is neutral or has a net magnetism of an even amplitude (neutral would be zero which is even). As a ball becomes more and more charged in one particular polarity it becomes more and more difficult to further polarize it in that direction, as it begins to resist the attachment of magnets in that orientation. After putting 5 magnets on a ball in the same orientation it is nearly impossible to put a sixth on the same way.

This is all quite interesting, and these things also behave quite unlike most objects that we are used to interacting with in our day-to-day lives; magnets are just weird, and that's why they're so awesome and fun to play with. After a while, though, it does become pretty intuitive, and I noticed these mechanics I've described leads to quite a cool little problem.

A magnetic structure built out of these elements is clearly easily represented as a graph. A ball is simply a vertex which may be connected with other balls with magnets, which are the edges. There are two ways in which an edge may be oriented, so obviously we've got a directed graph rather than the vanilla variety. This is all fine but I do get a bit caught up on how to represent the adding up of magnetization. I think if I set a convention where an outbound vertex represents a north-south magnet, i.e. the arrow is the south end, and the net magnetism is an integer with positive values representing net north magnetism, then I can evaluate the net magnetism of a vertex with $outdegree - indegree$.

As I went about "solving the puzzle" of the kit which is to use all the magnets and balls to construct a truncated octahedron, I always found myself wanting to arrange the magnets in a way that would minimize the net magnetism at each ball. It was a kind of OCD tendency to try to put the thing into the most "stable" or "natural" condition possible. But I noticed that each time I completed the shape, many of the balls which do have an even number of magnets connected to them did end up with a net magnetism. It seemed like a nontrivial problem to accomplish what I wanted.

Now, some formal math and computer science schooling (and a wasted summer) later I find that I still can't easily get the magnets into an optimal or near-optimal configuration by trial and error or a greedy method (that being simply letting the magnets attach based on their preferred orientation to the ball's current magnetization). So I am trying to model it mathematically because I suspect there may be a feasible algorithm; I'd like to know if the problem is NP-complete or not, but to do that I must first model it correctly.

So this is an optimization problem. I'm not exactly sure how to formally specify it as such but I'll give it a try. The set of instances is the set of digraphs which is the same shape as the graph representing the geometry of the construction. Being able to flip each magnet either way, this gives a maximum of $2^m$ possibilities, although accounting for symmetry it's very likely a much smaller set. Here the wikipedia article confuses me a little, it talks about the set of feasible solutions given an instance, but I can't tell what the difference between an instance and a feasible solution is, as it pertains to this particular problem. I define a function on vertices $M:V\rightarrow\mathbb{Z}$ where $M(v)=outdeg(v)-indeg(v)$. My goal is to minimize the sum of the magnitude of $M$ on all vertices: $min \displaystyle\sum_V|M|$

I have no idea what the next step is to figuring out the hardness of the problem. Do I propose algorithms, and through analysis of them determine a bound on the computation necessary to produce a result?

-
You could try to reduce some standard NP-complete problem like 3-SAT to this by finding a way to (polynomially) map its clauses onto the vertices or something like that. –  joriki Aug 29 '11 at 14:44

Note that in any graph which is Eulerian — in which every edge may be covered by a single closed walk, without repetition of edges — you can trivially achieve zero magnetization: simply direct all edges along the walk (which is an Eulerian tour).

Furthermore, in a directed graph, having equal in- and out-degrees is equivalent to having an Eulerian tour.

Algorithms to find Eulerian tours in graphs is a well-worn old subject of study, and can be done in linear time in the size of the graph (counting nodes and edges).

-
This is definitely along the lines of what I was looking for. I wonder if the notion of Eulericity might be expanded gracefully somehow. I don't think I can do it sensibly –  Steven Lu Aug 29 '11 at 15:07

Building on Niel de Beaudrap's answer, you can easily achieve a solution with minimal magnetization as follows:

Start with the undirected graph where each vertex represents a ball and each edge represents a magnet.

First, take all the vertices with odd degree, and divide them arbitrarily into pairs. (There will always be an even number of such vertices, since the total sum of degrees must be even.) Add an extra edge between the vertices in each pair.

The graph with the extra edges now has only nodes of even degree, and is therefore Eulerian. Find an Euler circuit in it, and assign directions to the edges along the circuit. After removing the extra edges, all the nodes with even degree will have zero magnetization, while those with odd degree will have magnetization $\pm 1$.

Also note that you don't even have to find an actual Euler circuit — any collection of cycles passing through every edge once is enough. It's very easy to find such a collection by a greedy algorithm: start at any node with untraversed edges, and keep moving along such edges until you end up where you started. Repeat until all edges have been traversed.

-