# a colouring / matching problem

While trying to find a bijection which preserves various combinatorial statistics, I was led to the problem below. Very much to my surprise, a closely related question, Coloring summands of given n-partition with given weights of colors, was asked here almost the same day I stumbled across the problem.

I have a number of boxes, each with a number of items in it, and a number of coloured tags. The total number of items equals the total number of coloured tags.

Essentially, Coloring summands of given n-partition with given weights of colors asks how to find the number of possibilities to assign the tags to the items, such that the items in one box all have the same colour.

I have to consider the following variant: each item has additionally a number written on it and so has each coloured tag.

I am in need of a reasonably efficient algorithm that decides whether one can assign the tags to the items in the boxes, such that

1. the number on the tag and on the item is always the same, and
2. the items in one box all have the same colour.

I am currently stuck with an instance of the problem that has roughly 350 boxes with a total of roughly 2800 items. The numbers on the tags range from 1 to 8 and there are 4 different colours.

Examples:

Suppose we have 4 boxes with items numbered either 1 or 2: \begin{array}{ccc} 1&1&1,\\ 1&1&2,\\ 1&2,&\\ 2&2.& \end{array} and colour tags blue with numbers 1,1,2,2,2 and red with numbers 1,1,1,1,2. Then there is a unique way to colour the boxes: first and last box red.

If the colour tags are blue with numbers 1,1,1,2,2 and red with numbers 1,1,1,2,2 then there are two ways to colour the boxes.

EDIT:

To facilitate playing with the problem, here is some python/sage code, including some examples, and the instance I am stuck with. I'll award the bounty to any presenter of an algorithm which yields a colouring in reasonable time (or proves that no such colouring exists)...

NEXT EDIT:

I discovered that it makes a huge difference in which order the colours are tried. The most natural heuristic is to try colours which have tags for all numbers still available first. The linked file reflects this finding.

ANOTHER EDIT:

A possibly helpful observation is that in the problematic instance, any box contains either 2 items, 4 items or 8 items. More precisely: there are 2 distinct boxes with 2 items, 11 distinct boxes with 4 items, the remaining boxes contain 8 items. Is there an obvious way to take advantage of this?

Is there any strategy to show that no solution exists?

• I don't follow: If all numbers are different, each item is assigned the color on the corresponding tag. The number of ways is therefore 0 or 1, depending on item distribution... If all numbers are the same, you have the original problem. So, you need to specify the restrictions on the extra numbers that you have. – Per Alexandersson Sep 19 '14 at 14:43
• Yes, the numbers written on the items are part of the problem specification. Indeed, if the numbers are all the same one obtains the original problem. Of course, if the multiset of numbers on the items does not agree with the multiset of numbers on the tags, there is no solution. But if it does, there need not be a solution either, of course. – Martin Rubey Sep 19 '14 at 15:02
• Oh, right, you look for an algorithm in the general case? It feels quite likely(?) that the general version can encode NP-complete problems, 3-SAT, or Knapsack... Equivalently, you can interpret you problem "tags with colors" but each item can only be colored with a subset of the colors. – Per Alexandersson Sep 19 '14 at 15:03
• Yes, I agree. I'd be already happy with an algorithm that solves the problem at hand... A naive recursive algorithm (that sorts the boxes such that boxes which require "rare" numbers come first) can do 90 boxes with a total of 600 items, 10 numbers and 3 colours in a few minutes... – Martin Rubey Sep 19 '14 at 15:24
• In practice, there are only very few colours and a little more numbers. – Martin Rubey Sep 19 '14 at 15:28

One extreme of few color and few numbers is two colors and only one number. With the further simplification that both colors occur equally often we get an NP-complete problem.

The Partition Problem is

Given a multiset $S=[x_1,\cdots,x_m]$ of positive integers with $\sum_S=\sum_1^mx_i=2N$, determine if $S$ can be partitioned into sub-multisets $S_1,S_2$ with $\sum_{S_1}=\sum_{S_2}=N.$

To reduce to your problem, Make $m$ boxes where box $B_i$ contains $x_i$ items each with numeral $1$ written on it. Also $N$ red and $N$ blue tags each with $1$ written on it.

Now it may be that in some sense, most instances are easy.

In various cases one might be able to ignore the tags or ignore the colors (and/or amalgamate to have only two colors or two tags). If any of those reduced problems has no solution , neither does the main problem. If one of them has only a few solutions then one has a few simpler problems to solve. But it seems like there is no hope of an all purpose efficient algorithm.

• Thank you! Yes, I'm not hoping for an efficient algorithm anymore, I just want to solve this one instance whose sizes I mentioned. I know already that ignoring the numbers this special instance has a solution. I'll have to think whether I can use this information (or reducing to two tags) without too much programming work, to see whether it possibly reduces running time. – Martin Rubey Sep 19 '14 at 19:01

Since you are looking for finding a feasible solution of a particular instance in a relatively short time, I would combine a couple techniques.

I would start by doing some breadth first searches, essentially finding small subsets of boxes and determining how many feasible colorings there are of each small subset. These would be exhaustive but quick, and the number of feasible colorings might serve to indicate what are the hard boxes to color.

Based on the data, I would then pick a feasible coloring and do a depth first search trying to extend the coloring as far as I could. If that started to look like it eats too much time, fix a coloring, and go back to the BFS strategy on the partially solved instance.

The distinction between this and attempting colorings at random is that you give yourself opportunity to study the instance and "game" the search towards possible or maximal success. Whether it is better to start with hard-to-color boxes or not is up to you and your sense of the instance.

There is also exploiting symmetry: if several boxes have the same contents, it may be prudent to leave those boxes out of the search and save them to the last, rather than generating many possible partial colorings involving those boxes.

Gerhard "Likes Feasible And Exhaustive Search" Paseman, 2014.09.19

• The above assumes there is a feasible solution you wish to find. If you want to prove that there is no feasible solution, I suspect finding a small infeasible subset of boxes is your best hope. Gerhard "Doesn't Like Infeasible So Much" Paseman, 2014.09.19 – Gerhard Paseman Sep 19 '14 at 23:13
• Actually, I'm not all that much interested in the solution itself, but rather whether a solution exists at all. I have no idea how to find a small infeasible subset. A possibly helpful observation is that any box contains either 2 items, 4 items or 8 iteme. More precisely: there are 2 distinct boxes with 2 items, 11 distinct boxes with 4 items, the remaining boxes contain 8 items. Is there an obvious way to take advantage of this? Besides, exploiting the symmetry was a very good idea: there are 356 boxes, but only 233 distinct boxes. I adapted the program to reflect this. – Martin Rubey Sep 24 '14 at 8:13
• If all the colors had a multiple of 8 labels, but every feasible coloring involved coloring the 2 distinct boxes of 2 items with different colors, you would get a mod 4 or mod 8 conflict. You can look for parity conflicts this way, or assume that they have to be resolved first and thus limit the available colorings of the "smallest" 13 boxes. At the moment, I see no other easy way to find a proof of infeasibility. Gerhard "Maybe Subtract Off Symmetric Boxes" Paseman, 2014.09.24 – Gerhard Paseman Sep 25 '14 at 1:02
• @Martin, how many mod 8 feasible colorings are there of the "smallest" boxes? In other words, how many ways are there of coloring the two boxes of two items and the four boxes of four items in such a way that when you are done, the remaining colors are each a multiple of 8? Also, do the "big" boxes fall into nice groups like half the boxes have numbers 1,2,3,4, 30% have numbers 6,7,8,10, and a much smaller remainder have some scattering? It may be that looking at the first six coordinates will suggest a coloring for the rest. Gerhard "Slicing Diagonally Might Also Help" Paseman, 2014.09.28 – Gerhard Paseman Sep 29 '14 at 5:36
• Unfortunately I cannot look into this right now myself - first week of teaching madness. (In case you really really want to, the code and the example are linked in the question...) Martin "A colouring would make me quite happy" Rubey :-) – Martin Rubey Sep 29 '14 at 7:23

Adding numbers does not make the problem (much) harder, I think. First, we remake the tags in new colors, corresponding to old color and number. Each item can then only be colored with a subset of new colors, which corresponds to that the old number on the tag and the item is the same.

Also, all items in one box must have the same color. Thus, in each box, we can find the biggest list of all valid colors we may color the items in that box with.

Thus, the problem can be reduced to the original problem about coloring boxes, but with some restrictions on what colors that are allowed for each box.

We can encode this as follows: Say you have $\lambda_i$ colors of color $i$, and $s_j$ items in box $j$. Then the number of valid colorings is given by the coefficient of $x_1^{\lambda_1}\dots x_k^{\lambda_k}$ in $$\prod_{j=1}^{boxes} (x^{s_j}_{c_{j1}}+x^{s_j}_{c_{j2}}+\dots+x^{s_j}_{c_{jm_j}})$$ where $c_{j1},c_{j2},\dots,c_{j{m_j}}$ are the valid colors to use in box $j$.

The right-hand side is a polynomial with degree equal to the total number of items. Extraction of the coefficient is theoretically possible with computing a high-order derivative of this... but it is most likely nasty.

• Although I like the algebraic formulation very nice, I do not see yet how it could save time. Expanding the polynomial is hopeless of course, the number of terms would grow exponentially with the number of boxes! – Martin Rubey Sep 19 '14 at 19:02
• Exactly... but sometimes (not in this case), it might be some trick to extract certain coefficients. It is an interesting technique in general, and several structure constants can be expressed as coefficients of some polyomial.. – Per Alexandersson Sep 19 '14 at 19:39