Quantidade mínima de cores impedindo um sub-triângulo uniformemente colorido

13

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 .nkφ:{(i,j)|ijn}{1,,k}(i,j),(i+l,j),(i+l,j+l)φ(i,j)=φ(i+l,j)=φ(i+l,j+l)

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):

                              Example

In fact they asked for a reasonably small k for n=1000 and in the solution (written in german) they noted that a greedy approach yields a coloring with 27 colors for n=1000, which can be reduced to 15 by randomizing colors until a valid solution is found.

I am interested into exact solutions (for smaller n). The solution says that backtracking yields that 2 colors are sufficient for n{2,3,4} and 3 are sufficient for 5n17, where backtracking is already really slow for n=17.

First I tried to use an ILP formulation and Gurobi to get some results for n>17, but it was too slow (already for n=17). 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 3 colors for n=18 within 10 minutes:

                              Solution with 3 colors for 18 nodes

But to decide if 3 colors suffice for n=19 it is already too slow. Is there some different approach that gives exact solutions for n19? Certainly we can't expect a polynomial algorithm.

Listing
fonte
interesting question. why do you say we can't expect a polynomial time algorithm?
Sasho Nikolov
@SashoNikolov it is just an assumption because this seems to be harder than finding a valid vertex coloring (harder in terms of more constraints), and vertex coloring is already a very hard problem.
Listing

Respostas:

10

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 partial c-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.)

enter image description here

Marzio De Biasi
fonte
Thank you for the solution of n=19. I tried it myself in the meantime and wrote a little STP program ( pastebin.com/efzHu5md ). Unfortunately it is not really faster than the direct SAT approach, I thus assume that it is possible to choose the inequalities better than I did.
Listing
4

Using a SAT-based approach, I can confirm every instance is 3-colorable up to n22. 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 for n=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 for n=22.

tri22-sol

Many thanks to Marzio for generating the image, and for letting me know about the problem! :-)

Juho
fonte