% Copyright 2007 by Till Tantau
%
% This file may be distributed and/or modified
%
% 1. under the LaTeX Project Public License and/or
% 2. under the GNU Public License.
%
% See the file doc/licenses/LICENSE for more details.

\documentclass{beamer}
%\usepackage[usenames]{color}
\usepackage{verbatim}
\usepackage{subfig}
  \usepackage{ifpdf}
  \usepackage{float}
  \usepackage{graphicx}
  \usepackage[noend, ruled, algo2e, noline]{algorithm2e}
  \linespread{1.5}
\definecolor{MyDarkBlue}{rgb}{0.1,0,0.55}
\def\gr4{\textcolor{OliveGreen}}
\def\re4{\textcolor{BrickRed}}
\def\bl4{\textcolor{MyDarkBlue}}
%\renewcommand{\labelitemi}{\fcolorbox{green}{Dandelion}{\color{Violet}{\textgreater}}}

\newcommand{\myskip}{\vskip 0.5cm \noindent}
  \newenvironment{uwaga}{%
       \begin{list}{}%
       {\setlength{\leftmargin}{1cm}}%
       \item[]%
        {\bf Uwaga!}\it
   }{%
       \end{list}
       \medskip
   }

%
% DO NOT USE THIS FILE AS A TEMPLATE FOR YOUR OWN TALKS¡!!
%
% Use a file in the directory solutions instead.
% They are much better suited.
%


% Setup appearance:

%\usetheme{Darmstadt}
\usefonttheme[onlylarge]{structurebold}
\setbeamerfont*{frametitle}{size=\normalsize,series=\bfseries}
\setbeamertemplate{navigation symbols}{}


% Standard packages

\usepackage[english]{babel}
\usepackage[latin1]{inputenc}
\usepackage{times}
\usepackage[T1]{fontenc}

\newcommand{\squares}{\textsf{sq}}
  \newcommand{\proot}{\textsf{root}}
  \newcommand{\II}{\mathit{Main}}
  \newcommand{\SQ}{\mathit{SQ}}
  \newcommand{\val}{\mathit{val}}
  \newcommand{\CC}{\mathcal{C}}
  \newcommand{\DD}{\mathcal{D}}
  \newcommand{\COMB}{\mathit{COMB}}


% Setup TikZ

\usepackage{tikz}
\usetikzlibrary{arrows}
\tikzstyle{block}=[draw opacity=0.7,line width=1.4cm]


% Author, Title, etc.

\title[The Maximum Number of Square Substrings in a Tree]
{%
  The Maximum Number of Square Substrings in a Tree%
}

\author[Gramm, Hartman, Nierhoff, Sharan, Tantau]
{
  {\textcolor{green!50!black}{M.Crochemore}}\inst{1} \and
  {\textcolor{green!50!black}{C. Iliopulos}}\inst{1} \and
  {\textcolor{blue}{T.Kociumaka}}\inst{2} \and
  {\textcolor{blue}{M.Kubica}}\inst{2} \and
 {\textcolor{blue}{ J.Radoszewski}}\inst{2}\and
  {\textcolor{blue}{W.Rytter}}\inst{2}\and
 { \textcolor{blue}{W.Tyczynski}}\inst{2}\and
  {\textcolor{blue}{T.Walen}}\inst{2}
  %\textcolor{green!50!black}{Till~Tantau}\inst{5}
}

\institute[King's College, London]
{
  \inst{1}%
  \textcolor{green!50!black}{King's College, London,UK.}
  \and
  \vskip-2mm
  \inst{2}%
  \textcolor{blue}{Warsaw University, Poland}
}

\date[LSD 2012]{LSD 2012}



% The main document

\begin{document}

\begin{frame}
  \titlepage
\end{frame}

\begin{frame}{Abstract}We show that the maximum number of different square substrings in undirected labeled trees
    behaves much differently than in words.
    A substring in a tree corresponds (as its value) to a simple path.
   \alert{ Let $\squares(n)$ be the maximum number of different square substrings in a tree of size $n$.}

    We show that asymptotically $\squares(n)$ is strictly between linear and quadratic orders,
    for some constants $c,c'>0$ we obtain:
   % \myskip
\alert{$$c\cdot n^{1+\frac{1}{3}} \le \squares(n) \le c'\cdot n^{1+\frac{1}{2}}.$$}
\end{frame}


\begin{frame}

\begin{figure}[h]
      \centering
      \includegraphics[width=5.7cm]{tree.png}
    \end{figure}
\vskip 1cm
{There are 4 square substrings in this tree.
        The longest is $acaaca$ and it corresponds to a path marked with
         a solid line.}
\end{frame}


\begin{frame}
In case of strings we can split the string into two halves and consider
squares contained fully
in of of these halves and squares overlapping the splitting  \textcolor{red!50!black}{middle point}.

In case of tree the middle point corresponds to a  \textcolor{red!50!black}{centroid}.

 \noindent
    For a tree $T$, we define a \emph{centroid} of $T$ as a node $R$ such
    that each component of $T \setminus\{r\}$ contains at most $n/2$ nodes.

 \textcolor{blue!50!black}{
    \begin{lemma}
      Each tree has a centroid that can be computed in linear time.
    \end{lemma}
    }
\end{frame}


\begin{frame}\textcolor{blue}{A comb} is a path of edges labeled with the letter $a$ called the \emph{backbone},
    with a number of \emph{branches} attached to different nodes in the backbone.
    Each such branch is a path starting with the letter $b$, followed by a number
    of $a$-labeled edges.
    % Our example of a tree with $\Omega(n^{4/3})$ square substrings from the previous
    % section belongs to this family.

    \begin{figure}[h]
      \centering
      \includegraphics{rys10_example-crop}
    \end{figure}


 {
        A comb containing 10 square substrings.
      }\label{fig:standard_comb}
\end{frame}

\begin{frame}%{How blocks help in perfect phylogeny haplotyping.}
   For $m=k^2$  define: $$Z_m\;=\; \{1,\ldots,k\} \cup \{i\cdot k\; :\; 1\le i\le k\}.$$
Each number $0 < j < m$ can be written
      % in a kind of a $\sqrt{m}$-system
      as $p\sqrt{m}-q$, where $0 \le p,q < \sqrt{m}$.
    \begin{lemma}\label{lem:dist}
      Assume $m$ is a square of a positive integer.
      Then for each $0 \le j < m$ there exist $u, v \in Z_m$ such that $u-v = i$.
    \end{lemma}
\myskip
    \noindent
   \textcolor{red}{DEFINITION:}\ \textcolor{blue}{ For $m=k^2$ we define a comb $T_m$ as follows:
    $T_m$ consists of a backbone of length $m$ with vertices numbered from 1 to $m$,
    and branches of the form $ba^m$ attached to each vertex $j \in Z_m$ of the backbone.}
\end{frame}

\begin{frame}{The structure of a comb $T_m$}
   \begin{figure}
      \centering
      \includegraphics[width=\textwidth]{rys1-crop}
    \end{figure}
\end{frame}

\begin{frame}
\begin{theorem}{\rm \bf [Lower Bound Theorem]}\\
      % {\bf (a)}\
      For each tree $T_m$ we have $\squares(T_m) = \Omega(|T_m|^{4/3})$.
      % \\
      % {\bf (b)}\  $\squares(n) =\Omega(n^{4/3})$.
      %
      % JR: the second part does not really seem relevant for the conference version.
    \end{theorem}

    \begin{proof}
      % First we prove point (a).
      From the Lemma, for every $1 < j < m$ there are two nodes $u,v$ of degree 3 on the backbone, with $\mathit{distance}(u,v)=j$.
      Hence, $T_m$ contains all squares of the form $(a^i b a^{j-i})^2$ for $0 \le i \le j$ and $0 < j < m$.
      Altogether this gives $\Omega(m^2)$ different squares.
      Note that $|T_m|=O(m\sqrt{m})$.
      Hence, the number of square substrings in $T_m$ is $\Omega(|T_m|^{4/3})$.
      %
      % We can now complete the proof by noticing that for $n$ which are not of the form $m\sqrt{m}$
      % we can take the tree $T_m$, where $m$ is the largest number such that
      % $m\sqrt{m}$ is not exceeding $n$.
      % Then we can add several dummy nodes to $T_m$ to have $n$ nodes.
      % We obtain a tree $T'$.
      % The bound $\Omega(|T'|^{4/3})$ applies now to the number of square substrings of this tree.
      % This completes the proof of point (b) and also of the the
      % whole theorem.
    \end{proof}
\end{frame}

\begin{frame}
    \noindent
    The squares of the form $(\;a^iba^j\;)^2$ correspond to paths ending in different branches,
   consequently  we obtain the following observation.
   \myskip
    {\bf Observation}

      For each vertex $v$ in a comb of size $n$, there are $O(\sqrt{n})$
      squares, which are values of paths starting at $v$.
      (This is a tight bound).
      \myskip
      This gives simple proof of the fact:

      The number of squares in a comb with $n$ nodes is $O(n^{3/2})$.
      \myskip We show much better upper bound.

\end{frame}

\begin{frame}
A comb contains only square substrings of the form $(a^i)^2$ or $(a^iba^j)^2$.
      The number of squares of the first type is $O(n)$.
      It is enough to bound the number of squares of the latter type, which we call \emph{special} squares. Any occurrence of a special square starts and ends within two different branches of a comb.
      Note that there are at most $n^{4/3}$ different special squares
      for which $i < n^{2/3}$ and $j < n^{2/3}$.

      A branch of a comb is called \emph{long} if it contains at least $n^{2/3}$ nodes.
      Note that there are $O(n^{1/3})$ long branches.
      Any occurrence of a long special square has at least one endpoint in a long branch.




\end{frame}

\begin{frame}%{continuation of the proof}
A comb contains only square substrings of the form $(a^i)^2$ or $(a^iba^j)^2$.
      The number of squares of the first type is $O(n)$.
      It is enough to bound the number of squares of the latter type, which we call \emph{special} squares. Any occurrence of a special square starts and ends within two different branches of a comb.
      Note that there are at most $n^{4/3}$ different special squares
      for which $i < n^{2/3}$ and $j < n^{2/3}$.

      A branch of a comb is called \emph{long} if it contains at least $n^{2/3}$ nodes.
      Note that there are $O(n^{1/3})$ long branches.
      Any occurrence of a long special square has at least one endpoint in a long branch.




\end{frame}
\begin{frame}{The square which starts at $u$ can finish at other branch
at most in one node  $v$.}
   \begin{figure}
      \centering
      \includegraphics[width=0.6\textwidth]{odbicie.png}
    \end{figure}
\end{frame}
\begin{frame}
 \begin{lemma}\label{lem:squares_comb}
      The number of squares in a comb with $n$ nodes is $O(n^{4/3})$.
    \end{lemma}


   \noindent
    {\bf PROOF}
  \
 It is enough to show:

 in any comb there are $O(n^{4/3})$
     (long)  square substrings $(a^iba^j)^2$,

      where $i \ge n^{2/3}$ or $j \ge n^{2/3}$

\noindent
      Consider a node $u$ located in a branch $B$ and a long branch $B'$.
      There is at most one occurrence of a long special square that starts in $u$ and
      ends within the branch $B'$.




      %Indeed, if there are $i$ $a$-labeled edges on the path from $u$ to the backbone
      %and $k$ edges on the path connecting the branches $B$ and $B'$ then the considered
      %square $(a^iba^{k-i})^2$ uniquely determines its other endpoint.

      Hence, the total number of long special squares is bounded by the number of nodes $u$
      multiplied by the number of long branches $B'$, that is, by $O(n^{4/3})$.


    \end{frame}



\begin{frame}
    \begin{lemma}
      For each vertex $v$ in a comb of size $n$, there are $O(\sqrt{n})$
      squares of the form $(a^iba^j)^2$, which are values of paths starting at $v$.
      (This is a tight bound).
    \end{lemma}
    \myskip
    PROOF.

    Assume $v$ is not on the horizontal spine. They are
    going to different vertical
    branches, however at different heights. These branches are disjoint.
    If we have $k$ such squares then we have $k$ different disjoint
    parts of the comb and these parts are pairwise disjoint.
    Hence $k\le \sqrt{n}$. The same argument
    applies to squares going from $v$ to te left.

\end{frame}

\begin{frame}
 Define a {\em double tree} $\DD=(T_1,T_2,R)$ as a labeled tree consisting of
  two disjoint (except one vertex) trees $T_1,T_2$ with a common root $R$.
  The size of $\DD$ is defined as $|\DD| = |T_1|+|T_2|$.
  In the double tree we consider only squares which start in $T_1$ and
  finish in $T_2$.


  A directed rooted labeled tree is deterministic if the edges outgoing
  from the same vertex have different labels.
  A double tree is deterministic if each of the trees $T_1$, $T_2$ treated as a
  directed tree with root $R$ is deterministic. A double deterministic tree
  is also called here a \emph{D-tree}. Such determinism will prove quite essential later.
  %The double tree in Fig.~\ref{D-tree} is deterministic.
\end{frame}

\begin{frame}{D-tree and a derived comb}

 \begin{figure}[t]
    \centering
    \includegraphics[width=\textwidth]{rys9_Dtree-crop}
  \end{figure}

  An example of a deterministic double tree (lower and upper trees), the anchor (root) is the red node.
  The squares of the form $(a^*ba^*)^2$ with $b$'s in both trees from a comb.
  \end{frame}


\begin{frame}
\begin{lemma}\label{lem:determ}
    For each double (possibly nondeterministic) tree there is a D-tree with
    at most the same number of vertices and the same number of square substrings
    (going from $T_1$ to $T_2$).
  \end{lemma}
  \begin{proof}
    Let us direct each tree $T_i$ temporarily from $R$ treated as a root.
    Assume we have a vertex $v$ with edges $(v,u)$, $(v,w)$ going to its children
    and labeled with same letter $a$.
    Then we can {\em glue} the vertices $u,w$.
    We can do it going top-down from the root in a BFS traversal.
  \end{proof}
\end{frame}

\begin{frame}
 We say that a path is anchored in $R\in T$ iff $R$ is an internal vertex of the path.
  A square is \emph{anchored} in $R$ iff it is a value of a path anchored in $R$.

  \begin{lemma}\label{lem:gdyby}{\rm \bf [Centroid Application Lemma]}
    Assume we know that maximum number of squares in any D-tree of size $n$ is
    $O(n^{\alpha})$, where $\alpha>1$.
    Then maximum number of squares in any tree is also $O(n^{\alpha})$.
  \end{lemma}
 \myskip
 PROOF.

    Let $T$ be a tree of size $n$ and let $R$ be its centroid.
    Consider a D-tree $(T_1,T_2,R)$ composed of determinized two copies $T_1$ and $T_2$ of $T$,
    %By the hypothesis there are $O(n^{\alpha})$ squares in the D-tree and
    % consequently also of squares in $T$ anchored in $R$.
\end{frame}

\begin{frame}
    Now we need to count the squares in $T$ that avoid the node $R$.
    After removing the node $R$, the tree is partitioned into small components $T_1,\ldots,T_k$
    Hence, the number of squares in $T$ can be written as:
    $$
      \squares(T) = O(n^{\alpha}) + \sum_i \squares(T_i),  \ \textrm{where}$$
    $$\sum_i |T_i|=n-1\ \&\ |T_i|\le n/2$$
    A solution to this recurrence yields the upper bound $\squares(n) = O(n^{\alpha})$.

\end{frame}


\begin{frame}
 There is a useful connection between D-trees and combs, as expressed by
  the following observation.

  \begin{lemma}\label{obs:D-trees-to-combs}
    Assume we have a D-tree labeled with letters $a,b$.
    Let us take only paths from each vertex in $T_1$, $T_2$ to $R$
    which contain at most one $b$, with other edges labeled wth $a$.
    Then the resulting labeled tree is a comb.
  \end{lemma}
\end{frame}

\begin{frame}
 \noindent
 We show only the upper bound for special squares.
  Assume binary alphabet $\{a,b\}$.

  \begin{theorem}
    The maximum number of special squares $(a^*ba^*)^2$ in any tree is $O(n^{4/3})$.
  \end{theorem}
  \begin{proof}
    It suffices to consider D-trees $\DD=(T_1,T_2,R)$ and only special squares
    which have one letter $b$ in $T_1$ and one letter $b$ in $T_2$.
    The number of other special squares going from $T_1$ to $T_2$ is linear.

  \end{proof}
\end{frame}

%-------------------------------------------------
\begin{frame}
Let $\DD=(T_1,T_2,R)$ be a D-tree.
  For a node $v \in T_1$ we define the set $\SQ(v)$ of all squares corresponding to paths from $T_1$ to $T_2$ which start in $v$
  and their centers are between $v$ and $R$.
  Each $xx \in \SQ(v,R)$ induces a period $|x|$ of $\val(v,R)$, thus $x$ admits a prefix 
  that is a border of $\val(v,R)$.

  \begin{figure}
    \centering
    \includegraphics[width=0.8\textwidth]{rysunek_pq.png}
    \caption{
      \label{fig:wrytter}
      Correspondance between squares in trees and borders.
    }
  \end{figure}
\end{frame}
  
\begin{frame}
  A $(p,q,z)$-comb is a D-tree that consists of a \emph{spine} path labeled with $(pq)^ap$ for some $a \ge 0$
  and \emph{branches} of the form $z(pq)^i$ for any non-negative integer $i$
  that can be attached after each $pq$ on the spine.
  The root $R$ of a comb divides the spine into non-empty parts $(pq)^bp$
  (lower part) and $(pq)^{a-b}$ (upper part).
  

%-------------------------------------------------

%-------------------------------------------------
\end{frame}
\begin{frame}

Hence, this occurrence of $xx$ induces a particular structure in the D-tree corresponding
  to occurrences of segments $p_iq_i$ and $z_i$ ($z_i=\varepsilon$ for $i=0$).
  This structure is called a $(p_i,q_i,z_i)$-comb in the D-tree rooted at $R$, denoted as $\COMB(p_i,q_i,z_i,\DD)$.
  Conversely, we say that $xx$ is induced by this comb.
 
  We assume that $p$, $q$, $z$ are words (possibly empty) such that $pq$ is non-empty and primitive,
  $qp$ is \emph{not} a prefix of $z$ and $pq$ is \emph{not} a suffix of $z$.
  The above definition of a generalized comb is valid if $z$ and $qp$ start with a different letter.
  If $z$ and $qp$ have a common prefix $x$, $z=xz'$, $qp=xw'$, then the branches are glued to the
  spine: that is, they have the form $z'(pq)^i$ and they can start between $x$ and $w'$
  within each $qp$.

\end{frame}
%-------------------------------------------------
%-------------------------------------------------
\begin{frame}
  \begin{figure}[htpb]
    \centering
    \includegraphics[width=.5\textwidth]{rys8_comb-crop}
    \caption{A $(p,q,z)$-comb with the root $R$
corresponds to a standard comb by substituting $pq\rightarrow a,\;
z\rightarrow b$.}
  \end{figure}
\end{frame}

%-------------------------------------------------
%-------------------------------------------------
\begin{frame}

  For each node $v$ in the lower tree there are $O(\log n)$
  possible combs corresponding to squares originating from this node and
  having center in a a lower tree.
  It can be shown that for a fixed $v$ these combs are disjoint.
  We have shown before that the number of squares starting from a given vertex in
  a standard comb $C$ is $O(\sqrt{|C|})$, this extends to generalized combs.
Hence there are $O(\sqrt{n})$ squares originating in a given, multiplying this by the number
of vertices we get $O(n^{3/2})$ squares in a D-tree. Due to the Centroid Application Lemma
taking $\alpha=3/2$  we get.

  \begin{theorem}\label{lem:squares_combs}
    The number of squares in a tree is $O(n^{3/2})$.
  \end{theorem}
\end{frame}
%-------------------------------------------------


\end{document}


