240 lines
7.8 KiB
TeX
240 lines
7.8 KiB
TeX
\begin{frame}{Table of contents}
|
|
\setbeamertemplate{section in toc}[sections numbered]
|
|
\setbeamertemplate{subsection in toc}[square]
|
|
\tableofcontents[sections={2}]
|
|
\end{frame}
|
|
|
|
|
|
\subsection{Idea}
|
|
|
|
\begin{frame}{Idea}
|
|
\setbeamercolor{block title}{fg=RoyalBlue!70}
|
|
\begin{block}{Theorem {\normalfont \small \color{black} \cite{bodlaender2010, gavril1974}}}
|
|
Equivalent:
|
|
\begin{enumerate}[(i)]
|
|
\item $G$ has a treewidth at most k.
|
|
\item There is an elimination ordering $\pi$, such that no vertex $v\in V$ has more than $k$ neighbours with a higher number in $\pi$ in $G^+_\pi$
|
|
\end{enumerate}
|
|
\end{block}
|
|
|
|
\setbeamercolor{block title}{fg=ForestGreen!70}
|
|
\begin{block}{Application}
|
|
\begin{enumerate}
|
|
\item Take \emph{some} elimination ordering $\pi$ of $G$
|
|
\item Construct $G^+_\pi$, calculate $k$
|
|
\item $\xrightarrow{(i)~\equiv~(ii)}$ Upper Bound for treewidth
|
|
\end{enumerate}
|
|
\end{block}
|
|
\end{frame}
|
|
|
|
\begin{frame}{What is $\bf G^+_\pi$ ?}
|
|
\metroset{block=transparent}
|
|
\begin{columns}[c]
|
|
\begin{column}{0.5\textwidth}
|
|
|
|
\begin{block}{}\centering
|
|
\begin{tikzpicture}
|
|
\node[shape=circle,draw=black] (A) at (0,0) {A};
|
|
\only<2>{\node[shape=circle,fill=mLightGreen] (A) at (0,0) {A};}
|
|
\only<3->{\node[shape=circle,fill=mDarkTeal,text=white] (A) at (0,0) {A};}
|
|
|
|
\node[shape=circle,draw=black] (B) at (3,0) {B};
|
|
\only<2>{\node[shape=circle,fill=mLightBrown] (B) at (3,0) {B};}
|
|
\only<3>{\node[shape=circle,fill=mLightGreen] (B) at (3,0) {B};}
|
|
\only<4->{\node[shape=circle,fill=mDarkTeal,text=white] (B) at (3,0) {B};}
|
|
|
|
\node[shape=circle,draw=black] (C) at (0,3) {C};
|
|
\only<2>{\node[shape=circle,fill=mLightBrown] (C) at (0,3) {C};}
|
|
\only<3>{\node[shape=circle,fill=mLightBrown] (C) at (0,3) {C};}
|
|
\only<4>{\node[shape=circle,fill=mLightGreen] (C) at (0,3) {C};}
|
|
\only<5->{\node[shape=circle,fill=mDarkTeal,text=white] (C) at (0,3) {C};}
|
|
|
|
\node[shape=circle,draw=black] (D) at (3,3) {D};
|
|
\only<3>{\node[shape=circle,fill=mLightBrown] (D) at (3,3) {D};}
|
|
\only<4>{\node[shape=circle,fill=mLightBrown] (D) at (3,3) {D};}
|
|
\only<5>{\node[shape=circle,fill=mLightGreen] (D) at (3,3) {D};}
|
|
\only<6->{\node[shape=circle,fill=mDarkTeal,text=white] (D) at (3,3) {D};}
|
|
|
|
\node[shape=circle,draw=black] (E) at (1.5,5) {E};
|
|
\only<4,5>{\node[shape=circle,fill=mLightBrown] (E) at (1.5,5) {E};}
|
|
\only<6>{\node[shape=circle,fill=mLightGreen] (E) at (1.5,5) {E};}
|
|
\only<7>{\node[shape=circle,fill=mDarkTeal,text=white] (E) at (1.5,5) {E};}
|
|
|
|
\path (A) edge (B);
|
|
\path (A) edge (C);
|
|
\path (B) edge (D);
|
|
\path (C) edge (D);
|
|
\path (C) edge (E);
|
|
|
|
|
|
\path[style=dashed, color=mLightBrown]<2> (B) edge (C);
|
|
\only<3->{\path[style=dashed, color=mDarkTeal] (B) edge (C);}
|
|
|
|
\path[style=dashed, color=mLightBrown]<4> (E) edge (D);
|
|
\only<5->{\path[style=dashed, color=mDarkTeal] (E) edge (D);}
|
|
\end{tikzpicture}
|
|
\end{block}{}
|
|
|
|
\begin{block}{}\centering
|
|
$\pi = [\textcolor<2>{mLightGreen}{A}
|
|
\textcolor<3>{mLightGreen}{,B}
|
|
\textcolor<4>{mLightGreen}{,C}
|
|
\textcolor<5>{mLightGreen}{,D}
|
|
\textcolor<6>{mLightGreen}{,E}]$
|
|
\end{block}{}
|
|
\end{column}
|
|
|
|
\begin{column}{0.5\textwidth}
|
|
\only<1-6>{
|
|
\begin{algorithm}[H]
|
|
\label{alg:fill}
|
|
\KwIn{$G, \pi$}
|
|
\KwOut{$G^+_{\pi}$}
|
|
$H=G$\\
|
|
\ForEach{$v\in V_G$}{
|
|
\ForEach{$w, x$ of N$_H$($v$)}{
|
|
\If{$\pi(w), \pi(x)>\pi(v)$}{
|
|
\alert<2->{add \{w,x\} to E$_H$}
|
|
}
|
|
}
|
|
}
|
|
\KwRet{H}
|
|
\end{algorithm}
|
|
}
|
|
|
|
\only<7>{
|
|
\begin{itemize}
|
|
\item $G^+_\pi$ is chordal
|
|
\item $G$ is a subgraph of $G^+_\pi$
|
|
\item $\pi$ is a perfect elimination ordering of $G^+_\pi$
|
|
\item $width$ of \emph{subtree graph} (also a tree decomposition) of $G^+_\pi$ is $\text{MAXCLIQUE}(G^+_\pi)-1$ ~\cite{gavril1974}
|
|
\item There is a tree decomposition algorithm for $G$ with $width = \text{MAXCLIQUE}(G^+_\pi)-1$, polynomial in n ~\cite{bodlaender2010}
|
|
\end{itemize}
|
|
}
|
|
|
|
\end{column}
|
|
\end{columns}
|
|
\end{frame}
|
|
|
|
\begin{frame}[c]
|
|
\centering
|
|
\alert{How to find \only<1,2>{the best}\only<3>{\sout{the best} a good} elimination ordering?}\\
|
|
|
|
\bigskip
|
|
|
|
\only<2>{
|
|
\begin{align*}
|
|
\text{Best} &= G^+_\pi~\text{with Min(MAXCLIQUE}(G^+_\pi))\\
|
|
&= \text{Computational Infeasible}\\
|
|
&= \text{see}~\cite{heggernes2006}
|
|
\end{align*}
|
|
}
|
|
|
|
\only<3>{
|
|
\small
|
|
No best. But the smaller the triangulation the better.\\
|
|
For minimal (not minimum): $\mathcal{O}(n^{2.376})$~\cite{heggernes2006}
|
|
}
|
|
\end{frame}
|
|
|
|
\subsection{Greedy Triangulation}
|
|
\begin{frame}{Greedy Triangulation - Algorithm}
|
|
\begin{algorithm}[H]
|
|
\label{alg:greedy}
|
|
\KwIn{$G(V,E)$}
|
|
\KwOut{$\pi$}
|
|
$H=G$\\
|
|
\For{$i=1$ \KwTo $n$}{
|
|
Choose $v \in H$ by criteria \alert<2>{X}\\
|
|
Set $\pi^{-1}(i) = v$\\
|
|
Eliminate $v$ from $H$ (make $N_H(v)$ a clique and remove $v$)
|
|
}
|
|
\KwRet{H}
|
|
\end{algorithm}
|
|
\bigskip
|
|
|
|
\uncover<2>{\centering \alert{How to choose X?}}
|
|
\end{frame}
|
|
|
|
\begin{frame}{Greedy Triangulation - Criteria X}
|
|
\metroset{block=transparent}
|
|
\begin{block}{Minimum Degree/Greedy Degree}
|
|
X = $v$ with smallest degree in $H$\\
|
|
\medskip
|
|
|
|
{\small Performs well in practice}
|
|
\end{block}
|
|
|
|
\begin{block}{Greedy Fill In}
|
|
X = $v$ which causes smallest number of fill edges in $G^+_\pi$\\
|
|
\hspace{1.8mm} = $v$ with smallest number of pairs of non-adjacent neighbours\\
|
|
\medskip
|
|
|
|
{\small Slightly slower, slightly better bounds than MD/GD on average}
|
|
\end{block}
|
|
|
|
\end{frame}
|
|
|
|
\begin{frame}{Greedy Triangulation - Advanced Criteria}
|
|
\metroset{block=transparent}
|
|
\begin{block}{Lower Bound Based}
|
|
Eliminate $v$ from $H$, compute lower bound (LB) of treewidth\\
|
|
Choose $v$ with Min($2*LB+\deg_H(v))$
|
|
\end{block}
|
|
|
|
\begin{block}{Enhanced Minimum Fill In}
|
|
Compute LB of $G$\\
|
|
Choose simplical or almost simplical $v$ with $\deg(v)$ at most LB\\
|
|
otherwise: Greedy Fill In
|
|
\end{block}
|
|
|
|
\dots{}
|
|
\end{frame}
|
|
|
|
\subsection{Local Search (Tabu Search)}
|
|
|
|
\begin{frame}[shrink]{Tabu Search}
|
|
\begin{block}{General Approach}
|
|
\begin{enumerate}[(i)]
|
|
\item Keep list of $\alpha$ last solutions to avoid cycling
|
|
\item Find inital solution [= some elimination ordering]
|
|
\item Make small change to get \emph{Neighbourhood}
|
|
\item Select neighbouring solution $\not\in \alpha$ with smallest cost
|
|
\item Repeat (iii), (iv) some time $\rightarrow$ return best solution
|
|
\end{enumerate}
|
|
\end{block}
|
|
|
|
\metroset{block=transparent}
|
|
\begin{block}{Neighbourhood Generation}
|
|
Swap two vertices in elminiation ordering
|
|
\end{block}
|
|
\begin{block}{Step Cost}
|
|
\begin{enumerate}[(i)]
|
|
\item Width of generated neighbour
|
|
\item But many neighbours with equal width, better:
|
|
$\rightarrow w_\pi * n^2 + \sum{v\in V}\vert N^+_\pi(v) \vert{}^2$
|
|
\end{enumerate}
|
|
\end{block}
|
|
|
|
\end{frame}
|
|
|
|
|
|
\subsection{Chordal Graph Recognition}
|
|
|
|
\begin{frame}{Chordal Graph Recognition Heuristics}
|
|
If it's chordal already, find perfect elminiation ordering (i.e. recognize it):
|
|
\begin{itemize}
|
|
\item Maximum Cardinality Search
|
|
\item Lexicographical Breadth First Search
|
|
\end{itemize}
|
|
\dots{} tree decomposition depends on (perfect) elimination ordering found. Mostly determined by algorithms, except for first chosen $v_n$ (from right to left).
|
|
|
|
$\rightarrow$ try for all $v$
|
|
|
|
$\rightarrow$ adds factor $\mathcal{O}(n)$
|
|
\end{frame}
|
|
|
|
%%% Local Variables:
|
|
%%% mode: latex
|
|
%%% TeX-master: "../upperbounds"
|
|
%%% End:
|