13
$\begingroup$

In the Bundeswettberweb Infomatik 2010/2011, there was an interesting problem:

For fixed $n$, find a minimal $k$ and a map $\varphi: \{(i,j)|i\leq j \leq n\}\rightarrow \{1,\ldots,k\}$, such that there is no triple $(i,j),(i+l,j),(i+l,j+l)$ with $\varphi(i,j)=\varphi(i+l,j)=\varphi(i+l,j+l)$.

Namely we are looking for the minimal amount of colors for a triangle, such that there is no uniformly colored equilateral subtriangle (the following picture shows an invalid coloring as the highlighted vertices form such an uniformly colored equilateral subtriangle):

$\ \ \ ~~~~~~~~~~~~~~~~~~~~~~~~~~~$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\in\{2,3,4\}$ and $3$ are sufficient for $5\leq n \leq 17$, 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 $n \geq 19$? Certainly we can't expect a polynomial algorithm.

$\endgroup$
  • $\begingroup$ interesting question. why do you say we can't expect a polynomial time algorithm? $\endgroup$ – Sasho Nikolov Jan 22 '14 at 19:50
  • $\begingroup$ @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. $\endgroup$ – Listing Jan 22 '14 at 20:04
10
$\begingroup$

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 \times 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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Listing Feb 13 '14 at 17:15
4
$\begingroup$

Using a SAT-based approach, I can confirm every instance is 3-colorable up to $n \leq 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 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! :-)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.