227 lines
13 KiB
TeX
227 lines
13 KiB
TeX
%! 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ść
|
|
|