Na razie nie wiemy, czy to zadanie znajdzie się w zbiorze i pod jakim numerem, ale jest szansa, że jako siódme zadanie z egzaminu w tym roku, pojawi się pod numerem 35+7, więc niech sobie tu na razie będzie.

To rozwiązanie bardzo mi się podoba, chociaż nie mam pewności, czy jest poprawne, bo jeszcze nie zostały sprawdzone nasze prace. Niemniej jest ciekawe i pokazuje pewien smaczek złożoności obliczeniowej, więc napiszę je dla potomnych.

Zadanie z grubsza (jeśli ktoś będzie potrzebował znać rozwiązanie, to będzie też znał formalną treść) polega na tym, żeby pokazać PTIME-owość problemu bardzo zbliżonego do 3COL z dodatkowym ograniczeniem: dla pewnego ułożenia wierzchołków grafu G na prostej, liczba krawędzi przechodzących nad, pod lub w(y)chodzących do/z każdego wierzchołka jest ograniczona przez ustalone L.

Wymyśliłem algorytm w O(n):

1. weź sobie dowolne miasto (no, wierzchołek) i wybierz te wszystkie (najwyżej) L krawędzi z nim związanych
2. wybierz te (najwyżej) 2L miast, które te krawędzi łączą
3. wybierz podgraf G złożony z tych miast i krawędzi łączących je ze sobą w G
4. dla takiego podgrafu zapuść bruta generującego wszystkie poprawne 5-kolorowania-miastami (czyli 3-kolorowania, ale treść zadania…), powiedzmy że on sobie działa w O(2^2^2^L) - bo jest max 2L miast
5. powtarzaj czynności 1-4 na kolejnych miastach, przy czym akumuluj wyniki na jednej liście… a więc jak masz dwa podgrafy G i dwie listy kolorowań im odpowiadające, to weź sklej te grafy krawędziami, których jeszcze nie wzięliśmy z G (a łączą miasta jednego podgrafu z miastami drugiego) i zrób nową listę kolorowań* - w ten sposób budowany podgraf będzie coraz większy, a lista kolorowań… niekoniecznie coraz krótsza, ale coraz bliższa liście kolorowań G
6. całość mającą złożoność zależną od L, które jest stałe, wykonałeś n razy, a więc O(n)

*Dlaczego to się da zrobić w czasie stałym? Ktoś bardzo dociekliwy zauważy, że jeśli te podgrafy są rozłączne, to nie tylko nie wystarczy wziąć przekroju list, ale jeśli ten „duży” podgraf ma prawie n miast, to może być 2^n krawędzi między podgrafami. No ale relax, to ograniczenie z L jest naprawdę bardzo silne. Popatrzmy: żeby zmerge'ować te listy będziemy iterować po krótszej, ona ma max 5^{2L} kolorowań. Dla każdego kolorowania będziemy mieć najwyżej 2L miast do zbadania. Każde z tych L miast ma co najwyżej L krawędzi wychodzących, z czego tylko niektóre idą do drugiego podgrafu. Każdy z jego L sąsiadów dostaje więc w tym momencie ustalenie, jakich kolorów nie może przybierać, żeby zachować zgodność z rozważanym kolorowaniem mniejszego podgrafu. No więc dla ustalonego kolorowania będziemy mieć 2L*L tych sąsiadów z powykluczanymi kolorami, zostanie więc max 5^{2L^2} kolorowań większego podgrafu, które pasują do tego naszego kolorowania. Bierzemy przekrój takiej listy z tą rzeczywistą listą możliwych kolorowań większego podgrafu i wrzucamy do nowej listy (możliwych kolorowań sumy tych podgrafów).

Całość działa oczywiście baaardzo wolno, ale liniowo ze względu na n, więc jesteśmy w P, qed.