106 lines
3.4 KiB
TeX
106 lines
3.4 KiB
TeX
\begin{frame}{General Motivation}
|
|
\begin{columns}[c]
|
|
\begin{column}{0.5\textwidth}
|
|
\begin{enumerate}
|
|
\item Choose infeasible problem
|
|
\begin{itemize}
|
|
\item Combinatorial Problems
|
|
\item Computational Biology
|
|
\item Constraint Satisfaction
|
|
\item \dots{}
|
|
\end{itemize}
|
|
\item Find FPT$_{tw}$ algorithm
|
|
\item Model problem as graph
|
|
\item Compute \emph{tree composition} with small \emph{tree width}
|
|
\uncover<2>{\alert{\item Tract the intractable}}
|
|
\end{enumerate}
|
|
\end{column}
|
|
|
|
\begin{column}{0.8\textwidth}
|
|
\begin{center}
|
|
\begin{tikzpicture}[xscale=1.5,yscale=1.6]
|
|
\tikzstyle{every node}=[]
|
|
\tikzstyle{every path}=[line width=0pt]
|
|
%
|
|
\begin{scope}
|
|
\draw[fill,green,opacity=1,line width=0]
|
|
(-1.5,0) -- (1.5,0)
|
|
(-1,0) .. controls (-.8,1) and (.8,1) .. (1,0);
|
|
;
|
|
%
|
|
\draw[fill,green!50,opacity=1,line width=0]
|
|
(-1,0) .. controls (-.8,1) and (.8,1) .. (1,0)
|
|
(1.1,0) .. controls (1.1,2.5) and (-1.1,2.5) .. (-1.1,0)
|
|
;
|
|
%
|
|
\draw[fill,red!50,opacity=1,line width=0]
|
|
(1.1,0) .. controls (1.1,2.5) and (-1.1,2.5) .. (-1.1,0)
|
|
(-1.2,0) .. controls (-1.2,3.5) and (1.2,3.5) .. (1.2,0)
|
|
;
|
|
%
|
|
\draw[fill,red!100,opacity=1,line width=0]
|
|
(-1.2,0) .. controls (-1.2,3.5) and (1.2,3.5) .. (1.2,0)
|
|
(1.5,0) .. controls (1.5,4.5) and (-3,4.5) .. (-1.5,0)
|
|
;
|
|
\draw[fill,red!100,opacity=1,line width=0]
|
|
(-1.2,0) .. controls (-1.2,3.5) and (1.2,3.5) .. (1.2,0)
|
|
(1.5,0) .. controls (3,4.5) and (-1.5,4.5) .. (-1.5,0)
|
|
;
|
|
%
|
|
\draw
|
|
(-1.5,0) -- (1.5,0)
|
|
(0,0.25) node[] {P}
|
|
(-1,0) .. controls (-.8,1) and (.8,1) .. (1,0)
|
|
%
|
|
(0,1.25) node[] {FPT}
|
|
(-1.1,0) .. controls (-1.1,2.5) and (1.1,2.5) .. (1.1,0)
|
|
%
|
|
(0,2.15) node[] {W[i]}
|
|
(-1.2,0) .. controls (-1.2,3.5) and (1.2,3.5) .. (1.2,0)
|
|
%
|
|
(-1,2.9) node[] {XP}
|
|
% (0,2.8) node[circle,black,fill,inner sep=0pt] {}
|
|
% (0,2.6) node[circle,black,fill,inner sep=0pt] {}
|
|
% (0,2.4) node[circle,black,fill,inner sep=0pt] {}
|
|
(-1.5,0) .. controls (-3,4.5) and (1.5,4.5) .. (1.5,0)
|
|
%
|
|
(1,2.9) node[] {paraNP}
|
|
% (0,2.8) node[circle,black,fill,inner sep=0pt] {}
|
|
% (0,2.6) node[circle,black,fill,inner sep=0pt] {}
|
|
% (0,2.4) node[circle,black,fill,inner sep=0pt] {}
|
|
(-1.5,0) .. controls (-1.5,4.5) and (3,4.5) .. (1.5,0)
|
|
;
|
|
\end{scope}
|
|
\end{tikzpicture}
|
|
\end{center}
|
|
\end{column}
|
|
\end{columns}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Why Upper Bounds?}
|
|
|
|
|
|
\metroset{block=fill}
|
|
\begin{block}{We want (efficiently)}
|
|
\begin{itemize}
|
|
\item \emph{High} Lower Bound: Tree dec. not the right tool
|
|
\item \emph{Low} Upper Bound: Tree dec. works
|
|
\item Other combinations? -- Not so useful
|
|
\end{itemize}
|
|
\end{block}
|
|
|
|
\begin{block}{What this paper is about}
|
|
\smallskip
|
|
Exact algorithm: Huge constant factor \cite{roehrig1998}
|
|
\begin{itemize}
|
|
\item[$\rightarrow$] Find a non-optimal tree decomposition
|
|
\item[$\rightarrow$] This is also an Upper Bound
|
|
\end{itemize}
|
|
\end{block}
|
|
|
|
\end{frame}
|
|
|
|
%%% Local Variables:
|
|
%%% mode: latex
|
|
%%% TeX-master: "../upperbounds"
|
|
%%% End:
|