%! TEX root = ../main.tex \section{25.01.2018 kolokwium \#2} \task Rozważ problem wyznaczania wartości indeksu chromatycznego $n$-wierzchołkowego grafu $G$, czyli $\chi'(G)$. Uzasadnij prawdziwość lub fałszywość następujących twierdzeń dotyczących tego problemu. \subtask Istnieje algorytm 1-absolutnie aproksymacyjny o złożoności $O(n)$ \label{subtask:1-2018:1:abs} \subtask Istnieje algorytm $\frac{3}{2}$-względnie aproksymacyjny \label{subtask:1-2018:1:32approx} \subtask Istnieje algorytm $\frac{4}{3}$-względnie aproksymacyjny \label{subtask:1-2018:1:43approx} \subtask Istnieje algorytm $\frac{5}{4}$-względnie aproksymacyjny \label{subtask:1-2018:1:54approx} \subtask Istnieje schemat aproksymacyjny o złożoności niewielomianowej \label{subtask:1-2018:1:nptas} \subtask Istnieje całkowicie wielomianowy schemat aproksymacyjny \label{subtask:1-2018:1:fptas} \begin{solution} W rozwiązaniu tego wykorzystamy twierdzenie vizinga mówiące, że każdy graf da się pokolorować $\Delta$ bądź $\Delta + 1$ kolorami. Na tej podstawie w podpunkcie \ref{subtask:1-2018:1:abs} możemy ułożyć algorytm, który zawsze zwraca wartość $\Delta + 1$ i będzie on $1$-absolutnie aproksymacyjny. Jednak pozostaje kwestia złożoności obliczeniowej wyznaczanie maksymalnego stopnia w grafie jest zadaniem zależnym od struktury danych. I tak w wypadku macierzy sąsiedztwa będzie to $\Theta(n^2)$ a w wypadku pęków $O(n)$ - czli się da. Dlatego na podpunkt \ref{subtask:1-2018:1:abs} odpowiedź to \textbf{TAK}. \begin{table}[H] \centering \begin{tabular}{r|r} $A_\text{opt}$ & $A$ \\\hline 1 & 2 \\ 2 & 3 \\ 3 & 4 \\ 4 & 5 \\ $\vdots$ & $\vdots$ \end{tabular} \caption{Tabela najgorszych odpowiedzi, jakie udzieli nasz algorytm} \end{table} Na ten moment nasz algorytm w najgorszym wypwadku (pierwszym) myli się 2-krotnie. Czy jesteśmy w stanie scharakteryzowac wszystkie grafy, które da się pokolorowac 1 kolorem tak, abyśmy mogli sprawdzić ten fakt wielomianowo? Tj. czy sprawdzenie $\chi'(G) = 1$ należy do \P? Tak, pokolorowanie jednym kolorem będzie możliwe tylko wypadku gdy z każdym wierzchołkiem jest związana tylko jedna krawędź - czyli $\Delta = 1$. \begin{table}[H] \centering \begin{tabular}{r|r} $A_\text{opt}$ & $A$ \\\hline 1 & $\not 2$ 1 \\ 2 & 3 \\ 3 & 4 \\ 4 & 5 \\ $\vdots$ & $\vdots$ \end{tabular} \end{table} Teraz nasz algorytm w najgorszym wypadku dla poprawnej odpowiedzi wynoszącej $2$ zwraca $3$ - czyli jest $\frac{3}{2}$-aproksymacyjny. Zatem odpowiedź na podpunkt \ref{subtask:1-2018:1:32approx} to \textbf{TAK}. Idźmy więc dalej, czy jesteśmy w stanie scharakteryzować wszystkie grafy, które da sie pokolorować max 2 koloroami? Na pewno wiemy, że muszą to być grafy o $\Delta = 2$, jednak nie jest to warunek wystarczajacy. \begin{figure}[H] \centering \begin{tikzpicture} \foreach \pos[count=\i] in {(1,0),(-1,0),(0,1.73)} \node[vertex] (\i) at \pos {}; \draw[red] (1) -- (2); \draw[green] (1) -- (3); \draw[blue] (3) -- (2); \end{tikzpicture} \caption{Trójkąt to graf o $\Delta = 2$, jednak potrzebuje 3 kolorów do poprawnego kolorowania krawędziowego} \end{figure} Okazuje się, że wszystkie ściezki da się pokolorować krawędziowo dwoma kolorami, oraz wszystkie cykle parzyste. Zatem jeżeli nasz graf składa się tylko z cykli parzystych oraz ścieżek - da się go pokolorować krawędziowo dwoma kolorami. Aby sprawdzić ten fakt, wystarczy rozbić graf na składowe spójności co możemy zrobić zwykłym \proc{DFS}-em lub \proc{BFS}-em a następnie sprawdzić czy są cyklami parzystymi bądź ścieżkami. \begin{table}[H] \centering \begin{tabular}{r|r} $A_\text{opt}$ & $A$ \\\hline 1 & $\not 2$ 1 \\ 2 & $\not 3$ 2 \\ 3 & 4 \\ 4 & 5 \\ $\vdots$ & $\vdots$ \end{tabular} \end{table} Teraz najgorszym przypadkiem jest para 3 i 4, czyli algorytm jest $\frac{4}{3}$-aproksymacyjny. Stąd odpowiedź na podpunkt \ref{subtask:1-2018:1:43approx} to \textbf{TAK}. Dla kolorowania 3 kolorami nie ma już możliwosci sprawdzenia wielomianowego - i to jest rzecz, którą albo musimy wiedzieć, albo wyczytać z książki. Zatem nie jesteśmy w stanie bardziej ulepszyć tej aproksymacji, a co za tym idzie nie jest on $\frac{5}{4}$ aproksymacyjny, czyli dla \ref{subtask:1-2018:1:54approx} odpowiedź to \textbf{NIE}. Każdy problem z klasy \NP można rozwiązać algorytmem deterministycznym w czasie niewielomianowym. Jeżeli jestesmy w stanie rozwiązać problem w czasie niewielomianowym - to na pewno jesteśmy też go w stanie aproksymować, choćby przez mnożenie dokładnego wyniku przes stałą. Dla podpunktu \ref{subtask:1-2018:1:nptas} odpowiedź to \textbf{TAK}. Problem ten jest problemem minimalizacyjnym, zatem gdyby istniał FPTAS to bylibysmy w stanie przybliżyć jego rozwiązanie z dowolną dokładnością: \begin{equation*} 1 \leq \frac{A_{opt}}{A} \leq 1 + \varepsilon \end{equation*} \begin{equation} A \leq A_{opt} \leq A + A\varepsilon \end{equation} Ponieważ odpowiedź na nasz problem jest liczbą całkowitą to wystarczy, że $A\varepsilon < 1$. Z Vizinga wiemy, że \begin{equation} A \leq \Delta + 1 \iff \frac{1}{\Delta + 1}A \leq 1 \end{equation} Czyli jeżeli tylko $\varepsilon < \frac{1}{\Delta + 1}$ to będziemy w stanie wywnioskować odpowiedź dokładną. Zatem schemat FPTAS może istnieć tylko jeżel $\P = \NP$. \end{solution} \task Problem istnienia cyklu Hamiltona w grafie $G$ należy do klasy \NP. Udowodnij ten fakt. \begin{solution} Aby udowodnić, że problem jest w \NP należy udowodnić, że istnieje taki certyfikat rozwiązania problemu, że będziemy w stanie potwierdzić poprawność tego rozwiązania w czasie wielomianowym. W tym wypadku takim certyfikatem może być lista wierzchołków po których powinnismy przechodzić po kolei. Sprawdzenie czy żaden wierzchołek się nie powtarza może być wykonane w czasie wielomianowym, tak samo sprawdzenie czy między kazdymi wierzchołkami istnieje połączenie. Nie musimy dowodzić tego, że problem ten jest \NPC, więc nie jest tu potrzebna $\alpha$-redukcja. \end{solution} \task Wypełnij poniższą tabelę wpisując do niej \textbf{TAK}, \textbf{NIE}, \textbf{NW} (Nie Wiadomo). \begin{table}[H] \centering \begin{tabular}{rl|c|c} & klasa & Weryfikowalne \dag & Rozwiązywalne \dag \\\hline \subtask & \P & & \\ \subtask & \NP & & \\ \subtask & \NPC & & \\ \subtask & \NP-trudne & & \\ \end{tabular} \end{table} \noindent\dag\ w czasie wielomianowym \note{W niektórych wypadkach więcej niż jedna odpowiedź jest poprawna} \begin{solution} Z definicji, problemy klasy \P da się rozwiązać w czasie wielomianowym - a ponieważ da się je rozwiązać to również da sie sprawdzić poprawnosć rozwiązania (wystarczy rozwiązać i porównać) w czasie wielomianowym. Wiadomo, że wszystkie problemy z klasy \NP są weryfikowalne w czasie wielomianowym - nie wiemy natomiast czy problemy te możemy w czasie wielomianowym rozwiązać. Jednak należy pamiętać, że klasa $\P \subseteq \NP$ - zatem w klasie \NP z pewnością są też problemy, które możemy rozwiązać w czasie wielomianowym. Ponieważ $\NPC \subseteq \NP$ to na pewno ich rozwiązania da się zweryfikować w czasie wielomianowym. Gdybyśmy wiedzieli jednak, że jakiegoś problemu \NPC nie da się rozwiązać w czasie wielomianowym to znaczyłoby to, że $\P \neq \NP$, podobnie gdybyśmy wiedzieli, że któryś problem \NPC da się rozwiązać w czasie wielomianowym to na pewno prawdą byłoby, że $\P = \NP$. A że nie wiemy czy $\P = \NP$ tak też nie wiemy nic na temat rozwiązywalności problemów \NPC w czasie wielomianowym. Problemy \NP-trudne to problemy conajmniej tak trudne jak najtrudniejsze problemy w klasie \NP, zatem w pewnym sensie prawdą jest, że $\NPC = \NP \cap \NPH$. Stąd wynika, że w klasie \NPH na pewno są problemy, które da się zweryfikować w czasie wielomianowym, o których rozwiązaniu nic nie wiadomo. Ponieważ jednak są to propblemy \textit{conajmniej} tak trudne to klasa ta zawiera też problemy niealgorytmiczne, których nie da się ani rozwiązać ani zweryfikować w czasie rzeczywistym. \begin{table}[H] \centering \begin{tabular}{rl|c|c} & klasa & Weryfikowalne \dag & Rozwiązywalne \dag \\\hline \subtask & \P & \textbf{TAK} & \textbf{TAK} \\ \subtask & \NP & \textbf{TAK} & \textbf{TAK}, \textbf{NW} \\ \subtask & \NPC & \textbf{TAK} & \textbf{NW} \\ \subtask & \NP-trudne & \textbf{TAK}, \textbf{NIE} & \textbf{NW}, \textbf{NIE} \\ \end{tabular} \end{table} \end{solution} \task Algorytm \textit{Largest First} (\problem{LF}) dla kolorowania wierzchołków grafu maluje je zachłannie poczynając od wierzchołka o najwyższym stopniu i kończąc na weierzchołku o najniższym stopniu. \subtask Oszacuj złożoność obliczeniową algorytmu \problem{LF} jako funnkcję $n$ za pomocą symbolu $\Theta$ \subtask Udowodnij, że \problem{LF} optymalnie koloruje cykle $C_4$ i $C_5$ ale suboptymalnie $C_6$ \subtask Wykonaj algorytm \problem{LF} na załączonym grafie \subtask Udowodnij, że algorytm \problem{LF} nie jest aproksymacyjny, tj. nie istnieje stałą $c$ taka, że $\mathtt{LF}(G) \leq c \cdot \chi(G)$ \subtask Udowodnij, że \problem{LF} jest $k$-bezwzględnie aproksymacyjny i $l$-wzzględnie aproksymacyjny w odniesieniu do grafów kubicznych tj. ustal wartości k i l \task \textit{Kolorowanie Kosztowe} (\problem{KK}) polega na tym, że kolory mają swoje koszty $c_1 \leq c_2 \leq \ldots \leq c_n$ i za każdym razem, gdy kolorujemy kolejny wierzchołek, przydzielamy mu koszt tego koloru. Problem polaga na tym, by tak pokolrowoać graf aby sumaryczny koszt kolorowania $\text{skk}(G)$ wszystkich wierzchołków był jak najmniejszy. Udowodnij, że nawet jeżeli $c_1 = c_2 = \ldots = c_k \leq c_{k+1}$ to problem ten jest \NP-trudny. \begin{solution} Aby udowodnić, że problem jest \NP-trudny musimy udowodnić, że jego wersja decyzyjna jest \NPC. W wypadku tego problemu wersja decyzyjna może brzmiec następująco ,,Czy dany graf $G$ da się pokolorować kosztem $c$ zakładajac, że koszty kolorowań to $c_1, c_2, c_3, ...$, przy czym wiemy, że koszt $k$ pierwszych kolorów to $c_k$?''. Możemy zauważyć, że zadanie to jest bardzo podobne do zadania \ref{task:2:wpw} ze strony \pageref{task:2:wpw}. Spróbujmy zredukować więc problem kolorowania wierzchołkowego grafu (\problem{KOL}) do problemu \problem{KK}. \begin{figure}[H] \centering \input{gfx/kol-kk.tex} \caption{$\alpha$-redukcja z problemu \problem{KOL} do \problem{KK}} \end{figure} Zauważmy, że jeżeli wszystkie kolory, którymi kolorujemy graf mają ten sam koszt $1$ to łączny koszt pokolorowania tego grafu wyniesie $n$ (każdy wierzchołek kosztuje nas $1$, a wierzchołków jest $n$). Jeżeli natomiast jeden z kolorów miałby koszt większy niż $1$ to z pewnością łączny koszt kolorowania takiego grafu musiałby być również większy niż $n$. Wykorzystamy te zależność na swoją korzyść - jeżeli $k$ pierwszych kolorów będzie miało koszt $1$ a pozostałe będą droższe (załóżmy, że ich koszt to będzie 2) to koszt pokolorowania tego grafu $k$ kolorami wyniesie $n$. Jeżeli natomiast potrzebujemy więcej niż $k$ kolorów to będziemy musieli wykorzystać kolor o koszcie 2 czyli koszt jaki poniesiemy będzie na pewno większy niż $n$. Zatem graf da się pokolorować kosztem $n$ tylko kiedy graf da się pokolorować $k$ kolorami, gdzie koszt każdego koloru wynosi $1$. Nasza $\alpha$-redukcja będzie zatem następująca: \begin{equation*} G, k \rightarrow \underset{G}{G}, \underset{c}{n}, \underset{c_k}{1}, \underset{k}{k}, \underset{c_{k+1}}{2}, \underset{c_{k+2}}{2}, \ldots \end{equation*} \end{solution} \task Alicja jest częstym klientem sklepu \textit{SuperShop} i uzbierała 5 kuponów rabatowych o różnych wartościach zniżek. Ma zapisane na liście zakupowej $n$ produktów, które chce dzisiaj kupić oraz ich ceny. Chce pójść dzisiaj do sklepu bez gotówki i kupić wybrane produkty używajac tylko kuponów. Nie chce natomiast zmarnować żadnego kuponu, czyli używa tylko tych, których wartość zostanie w pełni wykorzystana. Zastnawia się czy istnieje zestaw produktów i odpowiednia kombinacja kuponów, by mogła pójść na zakupy i kupić cokolwiek? \note{Wszystkie kwoty są zaokrąglane do pełnych złotówek} \subtask Spróbuj ułożyć algorytm wielomianowy, który rozwiązuje ten problem \subtask Jeśli nie potrafisz, udowodnij jego \NP-zupełność