Úloha: Problém kliky je silne NP-úplný, pretože klika\(_n\) je rovnaký problém ako klika nakoľko \(k=\)number\((I)\leqq V\) pre všetky zmysluplné inštancie \(I=((V,E),k)\) problému kliky.

Úloha: Algoritmus Kostra

1. Nájdi minimálnu kostru \(T\) grafu \(G\) s maticou vzdialenosti \((d_{ij})\).
2. Vytvor multigraf \(G\) zdvojením každej hrany kostry \(T\).
3. Nájdi eulerovské spojenie grafu \(G\) a zahniezdenú cestu. Veta 4. Algoritmus Kostra je 1-aproximatívny algoritmus pre TSP.

Úloha: Christofides

1. Nájdi minimálnu kostru $T$ grafu $G$ s maticou vzdialeností \((d_{ij})\).
2. vrcholy \(T\), ktoré majú nepárny stupeň a kompletné spárenie \(M\) s minimálnym súčtom ohodnotení hrán v kompletnom grafe pozostávajúcom len z týchto vrcholov. Nech \(G'\) je multigraf s vrcholmi \(\{1,\dots,n\}\) a hranami patriace \(T\) a patriace \(M\).
3. Nájdi eulerovské spojenie a zahniezdenú cestu.