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

13

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

$\ \ \ ~~~~~~~~~~~~~~~~~~~~~~~~~~~$ Przykład

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: $3$ $n=18$ $10$

$\ \ \ ~~~~~~~~~~~~~~~~~~~~~~~~~~~$ Rozwiązanie z 3 kolorami dla 18 węzłów

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. $3$ $n=19$ $n \geq 19$

graph-theory sat combinatorics

— Wymienianie kolejno
źródło

interesujące pytanie. dlaczego mówicie, że nie możemy oczekiwać algorytmu wielomianowego czasu?

— Sasho Nikolov

@SashoNikolov to tylko założenie, ponieważ wydaje się to trudniejsze niż znalezienie prawidłowego zabarwienia wierzchołków (trudniejsze pod względem większej liczby ograniczeń), a zabarwienie wierzchołków jest już bardzo trudnym problemem.

— Wpis

10

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. $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.)

wprowadź opis zdjęcia tutaj

— Marzio De Biasi
źródło

Dziękuję za rozwiązanie . W międzyczasie spróbowałem i napisałem mały program STP ( pastebin.com/efzHu5md ). Niestety nie jest to tak naprawdę szybsze niż bezpośrednie podejście SAT, dlatego zakładam, że możliwe jest wybranie nierówności lepiej niż ja.

n = 19

$n=19$

— Wpis

4

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 \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=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! :-)

— Juho
źródło