Minimalna ilość kolorów zapobiegająca równobocznemu jednokolorowemu podtrószkowi

W Bundeswettberweb Infomatik 2010/2011 pojawił się interesujący problem:

Dla stałej znajdź minimalne i mapę , tak że nie ma potrójnego z .$n$$k$$\varphi: \{(i,j)|i\leq j \leq n\}\rightarrow \{1,\ldots,k\}$$(i,j),(i+l,j),(i+l,j+l)$$\varphi(i,j)=\varphi(i+l,j)=\varphi(i+l,j+l)$

Mianowicie szukamy minimalnej ilości kolorów dla trójkąta, tak aby nie było równomiernego podtekstu równobocznego (poniższy rysunek pokazuje nieprawidłowe zabarwienie, ponieważ podświetlone wierzchołki tworzą taki podjednostka o jednolitym kolorze):

$\ \ \ ~~~~~~~~~~~~~~~~~~~~~~~~~~~$

W rzeczywistości poprosili o rozsądnie małe dla a w rozwiązaniu (napisanym w języku niemieckim) zauważyli, że zachłanne podejście daje zabarwienie kolorów dla , które można zmniejszyć do przez losowe kolory, aż do znaleziono prawidłowe rozwiązanie.$k$$n=1000$$27$$n=1000$$15$

Interesują mnie dokładne rozwiązania (dla mniejszych ). Rozwiązanie mówi, że cofanie powoduje, że kolory są wystarczające dla a są wystarczające dla , gdzie cofanie jest już naprawdę wolne dla .$n$$2$$n\in\{2,3,4\}$$3$$5\leq n \leq 17$$n=17$

Najpierw próbowałem użyć formuły ILP i Gurobi, aby uzyskać wyniki dla , ale było to zbyt wolno (już dla ). Następnie użyłem solwera SAT , ponieważ zauważyłem, że istnieje prosta formuła jako instancja SAT.$n>17$$n=17$

Dzięki takiemu podejściu byłem w stanie wygenerować rozwiązanie z kolorami dla w ciągu minut:n = 18 $3$$n=18$$10$

$\ \ \ ~~~~~~~~~~~~~~~~~~~~~~~~~~~$

Ale aby zdecydować, czy kolory wystarczą dla , jest już zbyt wolny. Czy istnieje jakieś inne podejście, które daje dokładne rozwiązania dla ? Z pewnością nie możemy oczekiwać algorytmu wielomianowego.n = 19 n ≥ $3$$n=19$$n \geq 19$

Tylko rozszerzony komentarz:

Możesz spojrzeć na podejście zastosowane przez Steinbacha i Posthoffa, aby znaleźć 4-kolorowanie siatki 18x18 (i 12x21) bez monochromatycznych prostokątów :

Bernd Steinbach i Christian Posthoff, Rozwiązanie ostatniej otwartej czterokolorowej siatki bez prostokątów, niezwykle złożony problem o wielu wartościach . W tegorocznych 43. Międzynarodowym Sympozjum IEEE 2013 na temat logiki wielowartościowej (ISMVL '13)

Jak udowodnili Gasarch i in. biorąc pod uwagę częściowe zabarwienie dowolnego prostokąta , NP-zupełne jest podjęcie decyzji, czy zabarwienie można rozszerzyć na cały prostokąt bez prostokątów monochromatycznych: Daniel Apon, William Gasarch, Kevin Lawler, Problem NP-Complete w kolorowaniu siatki . Są więc duże szanse, że problem jest NP-zupełny nawet dla trójkątów równobocznych ... Myślę, że dobrym rezultatem byłoby udowodnienie tego.n × $c$$n \times m$

Tylko na marginesie: spędziłem tygodnie cykli procesora na problemie 4-kolorowania bez monochromatycznego prostokąta, ale zacząłem od błędnego wyniku częściowego (zła poprzednia analiza, która ograniczała liczbę możliwych 1-kolorowych podkonfiguracji) i użyłem Solver STP ograniczenia ; możesz osiągnąć wielkie ulepszenia, jeśli dodasz ograniczenia, które łamią symetrie (np. kolejność kolorowania boku trójkąta) i spróbujesz przeprowadzić analizę możliwych konfiguracji przy użyciu tylko 1 koloru.

EDYCJA: jest to wynik programu STP dla n = 19 (~ 1 min.)

Używając podejścia opartego na SAT, mogę potwierdzić, że każda instancja jest trójkolorowa do . Lokalny moduł wyszukiwania znajduje rozwiązanie dla nadal dość szybko na nowoczesnym komputerze stacjonarnym. Próbowałem tego samego podejścia dla , ale nie uzyskałem rozwiązania w ciągu około 96 godzin. Kusi zatem przypuszczenie, że nie jest już trójkolorowy. (Pozwolę sobie również zauważyć, że 4-kolorystyka jest natychmiast znajdowana dla ).n = 22 n = 23 n = 23 n = $n \leq 22$$n=22$$n=23$$n=23$$n=23$

Moja obserwacja dla była podobna do twojej, to znaczy, wydaje się, że jest już poza zasięgiem kompletnego solvera, jeśli zastosuje się bezpośrednie kodowanie. Z drugiej strony nie zdziwiłbym się, gdyby mądrzejsze kodowanie rozwiązało przypadek (i dalej?).n = $n=19$$n=23$

Poniżej znajduje się rozwiązanie dla .$n=22$

Ogromne podziękowania dla Marzio za wygenerowanie obrazu i poinformowanie mnie o problemie! :-)