No Bundeswettberweb Infomatik 2010/2011, havia um problema interessante:
Para fixo , encontre um mínimo de e um mapa , de modo que não haja triplo com .
Ou seja, estamos procurando a quantidade mínima de cores para um triângulo, de modo que não exista um sub-triângulo equilateral uniformemente colorido (a figura a seguir mostra uma coloração inválida, pois os vértices realçados formam um sub-triângulo equilateral uniformemente colorido):
In fact they asked for a reasonably small for and in the solution (written in german) they noted that a greedy approach yields a coloring with colors for , which can be reduced to by randomizing colors until a valid solution is found.
I am interested into exact solutions (for smaller ). The solution says that backtracking yields that colors are sufficient for and are sufficient for , where backtracking is already really slow for .
First I tried to use an ILP formulation and Gurobi to get some results for , but it was too slow (already for ). Then I used a SAT solver, because I noticed that there is a straight forward formulation as a SAT-instance.
With that approach I was able to generate a solution with colors for within minutes:
But to decide if colors suffice for it is already too slow. Is there some different approach that gives exact solutions for ? Certainly we can't expect a polynomial algorithm.
fonte
Respostas:
Just an extended comment:
You can take a look to the approach used by Steinbach and Posthoff to find the 4-coloring of a 18x18 (and 12x21) grid without monochromatic rectangles:
Bernd Steinbach and Christian Posthoff, Solution of the Last Open Four-Colored Rectangle-free Grid an Extremely Complex Multiple-Valued Problem. In Proceedings of the 2013 IEEE 43rd International Symposium on Multiple-Valued Logic (ISMVL '13)
As proved by Gasarch et al. given a partialc -coloring of an arbitrary n×m rectangle, it is NP-complete to decide if the coloring can be extended to the whole rectangle without monochromatic rectangles: Daniel Apon, William Gasarch, Kevin Lawler, An NP-Complete Problem in Grid Coloring.
So there are high chances that the problem is NP-complete even for equilateral triangles .... I think it would be a nice result to prove it.
Just a side note: I spent weeks of CPU cycles on the monochromatic rectangle-free 4-coloring problem but I started from a wrong partial result (a wrong previous analysis that restricted the number of possible 1-color sub-configurations) and I used the STP constraint solver; you can achieve great improvements if you add constraints that break symmetries (e.g. an ordering on the coloring of a side of the triangle) and try to make an analysis of the possible configurations using only 1-color.
EDIT: this is the result of an STP program for n=19 (~ 1 min.)
fonte
Using a SAT-based approach, I can confirm every instance is 3-colorable up ton≤22 . A local search solver finds a solution for n=22 still rather quickly on a modern desktop. I tried the same approach for n=23 , but obtained no solution in about 96 hours. It is thus tempting to conjecture that n=23 is not 3-colorable anymore. (Let me also remark that a 4-coloring is found instantly for n=23 ).
My observation forn=19 was similar to yours, that is, it already seems quite out of reach for a complete solver if the straightforward encoding is used. On the other hand, I wouldn't be surprised if a smarter encoding could settle the case of n=23 (and beyond?).
Below is the solution forn=22 .
Many thanks to Marzio for generating the image, and for letting me know about the problem! :-)
fonte