% Template article for preprint document class `elsart'
% SP 2001/01/05

% Modified 2007/01/09 for CTW 2010
% Please find the original file at http://www.elsevier.com/

\documentclass{ctwart}

% Use the option doublespacing or reviewcopy to obtain double line spacing
% \documentclass[doublespacing]{elsart}

% if you use PostScript figures in your article
% use the graphics package for simple commands
% \usepackage{graphics}
% or use the graphicx package for more complicated commands
% \usepackage{graphicx}
% or use the epsfig package if you prefer to use the old commands
% \usepackage{epsfig}

% The amssymb package provides various useful mathematical symbols
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{bbm}
\usepackage{epsfig}
\usepackage{psfrag}
\usepackage{rotating}
%\usepackage{a4wide}
\usepackage[square,comma,numbers]{natbib}

\begin{document}
\setcounter{page}{17}
\begin{frontmatter}

% Title, authors and addresses

% use the thanksref command within \title, \author or \address for footnotes;
% use the corauthref command within \author for corresponding author footnotes;
% use the ead command for the email address,
% and the form \ead[url] for the home page:
% \title{Title\thanksref{label1}}
% \thanks[label1]{}
% \author{Name\corauthref{cor1}\thanksref{label2}}
% \ead{email address}
% \ead[url]{home page}
% \thanks[label2]{}
% \corauth[cor1]{}
% \address{Address\thanksref{label3}}
% \thanks[label3]{}

\title{Exact Bipartite Crossing Minimization under Tree
  Constraints\thanksref{financialaid}}
\thanks[financialaid]{ Financial
    support from the German Science Foundation (DFG) is acknowledged under
    contracts Bu~2313/1--1 and Li~1675/1--1.}
% use optional labels to link authors explicitly to addresses:
% \author[label1,label2]{}
% \address[label1]{}
% \address[label2]{}

\author[label1]{Frank Baumann}
\author[label1]{Christoph Buchheim}
\author[label2]{Frauke Liers}

\address[label1]{Technische Universit\"at Dortmund, Fakult\"at f\"ur
  Mathematik, Vogelpothsweg 87, 44227 Dortmund, Germany}
\address[label2]{Universit\"at zu K\"oln, Institut f\"ur Informatik,
  Pohligstra\ss e 1, 50969 K\"oln, Germany}

\begin{keyword}
tanglegram \sep crossing
  minimization \sep quadratic programming 
\end{keyword}

\end{frontmatter}

% main text

\section{Abstract}
\label{abstract}
A \emph{tanglegram} consists of a pair of (not necessarily binary)
trees. Additional edges, called \emph{tangles}, may connect the leaves
of the first with those of the second tree. The task is to draw a
tanglegram with a minimum number of tangle crossings while making sure
that the trees are drawn crossing-free. This problem has relevant
applications in computational biology, e.g., for the comparison of
phylogenetic trees. Most existing approaches are only applicable for
binary trees. In this work, we show that the problem can be formulated
as a quadratic linear ordering problem (QLO) with side constraints. In
\cite{bwz07} it was shown that, appropriately reformulated, the QLO
polytope is a face of some cut polytope. It turns out that the
additional side constraints do not destroy this property. Therefore,
any polyhedral approach to max-cut can be used in our context. We show
that our approach is very efficient in practice for both random and
real-world binary as well as general tanglegrams.

\section{Introduction}
\label{Introduction}

The task of drawing tanglegrams arises in several relevant
applications, e.g., in computational biology for the comparison of
phylogenetic trees. Moreover, tanglegrams occur when analyzing
software projects in which a tree represents package, class and method
hierarchies. This application yields tanglegrams on trees that are not
binary in general~\cite{nhvw08}.
Most of the literature is concerned with the case of binary trees and
leaves that are in one-to-one correspondence. \cite{fkp09} showed the
NP-hardness of tanglegram layout, even in the case of binary
trees. Our approach, to be explained below, generalizes the exact
integer-programming (IP) approach of \cite{nhvw08} for binary
tanglegrams. In the latter, minimizing the number of tangle crossings
reduces to solving an unconstrained quadratic binary optimization
problem, which is well-known to be equivalent to a maximum cut problem
in some associated graph with an additional node~\cite{S88}. In an
undirected graph~$G=(V,E)$, the cut~$\delta(W)$ induced by a
set~$W\subseteq V$ is defined as the set of edges~$(u,v)$ such
that~$u\in W$ and~$v\not\in W$. If edge weights are given, the weight
of a cut is the total weight of edges in the cut. Now the maximum cut
problem asks for a cut of maximal weight or cardinality.
While in the recent paper by~\cite{vasg09} the focus is on binary
instances, a fixed-parameter algorithm for general tanglegram
instances is presented. According to our knowledge, this is the only
algorithm that could deal with non-binary trees; however, no
implementation or running times are provided making it impossible to
evaluate its practical performance.

\section{An Exact Model for General Tanglegrams}\label{sec:model}

Let~$G=(V_1\cup V_2,E)$ be a bipartite graph. The task is to draw $G$
with straight line edges. The nodes in~$V_1$ and~$V_2$ have to be
placed on two parallel lines~$H_1$ and~$H_2$ such that the number of
edge crossings is minimal. Assume for a moment that the nodes on the
$H_1$ are fixed, and only the nodes on $H_2$ are permuted. For each
pair of nodes on~$H_2$, we introduce a variable~$x_{uv}$ such
that~$x_{uv}=1$ if~$u$ is drawn to the left of~$v$ and~$x_{uv}=0$
otherwise. For edges~$(i,k)$ and~$(j,l)$ with~$i,j\in H_1$ and~$k,l\in
H_2$, such that~$i$ is left of~$j$, a crossing exists if and only
if~$l$ is left of~$k$. We thus have to punish~$x_{lk}$ in the
objective function. The task of minimizing the number of crossings is
now equivalent to determining a minimum linear ordering on the nodes
of~$H_2$. Note that bipartite crossing minimization with one fixed
layer is already NP-hard~\cite{EW94}.
If the nodes on both layers are allowed to permute, the problem can be
modeled as a quadratic optimization problem over linear ordering
variables. The quadratic linear ordering problem~(QLO) is
\begin{equation*}
  \begin{array}{rrcll}
    \min \quad & \multicolumn{4}{l}{\sum_{(i,j,k,l)\in I} c_{ijkl}x_{ij}x_{kl} }  \\[0.5ex]
    (QLO)\quad\quad \textrm{s.t.} \quad & x &\in& P_{LO}\\
     &x_{ij} &\in& \{0,1\} & \forall (i,j) \in J\\
  \end{array}%\label{QLO}
\end{equation*}
where $P_{LO}$ is the linear ordering polytope and
%   $I  =  \{ (i,j,k,l) \mid  i,j \in H_1, i<j,\;\mbox{and}\;k,l \in
%   H_2,k<l\}$ and 
%   $J  =  \{ (i,j) \mid  i,j \in H_1\;\mbox{or}\; i,j \in H_2,~i<j\}$.

 \begin{eqnarray*}
   I & = & \{ (i,j,k,l) \mid  i,j \in H_1,~i<j,\;\mbox{and}\;k,l \in H_2,~k<l\}\\
   J & = & \{ (i,j) \mid  i,j \in H_1\;\mbox{or}\; i,j \in H_2, i<j\}
 \end{eqnarray*}
We replace each product $x_{ij}x_{kl}$ by a new binary
variable~$y_{ijkl}$ and add the linearization constraints $y_{ijkl}
\leq x_{ij}, y_{ijkl}\leq x_{kl}, y_{ijkl} \geq x_{ij}+x_{kl}-1$. We
call the resulting linearized problem (LQLO).  In \cite{bwz07} it was
shown that a 0/1 vector~$(x,y)$ satisfying~$y_{ijkl}=x_{ij}x_{kl}$ is
feasible for (LQLO) if and only if
\begin{equation}
  x_{ik} -y_{ijik} -y_{ikjk} + y_{ijjk} = 0 \; \forall (i,j,k,l)\in I, 
  \label{eq:qlofaces}
\end{equation}
which is a quadratic reformulation of the constraints defining
$P_{LO}$.  Note that (LQLO) is a quadratic binary optimization problem
where the feasible solutions need to satisfy further side
constraints. As unconstrained binary quadratic optimization is
equivalent to the maximum cut problem~\cite{S88}, the task is to
intersect a cut polytope with a set of hyperplanes. \cite{bwz07}
showed that the hyperplanes~\eqref{eq:qlofaces} cut out faces of the
cut polytope.

Let us consider a triple of leaves $a,b,c$ in one of the trees. In
case all pairwise lowest common ancestors coincide, all relative
orderings between~$a$, $b$, and~$c$ are feasible. However, if the
lowest common ancestor of, say, $a$ and $b$ is on a lower level than
that of, say, $a$ and $c$, then~$c$ must not be placed between~$a$
and~$b$; see Figure~\ref{fig:intra_cross}.
\begin{figure}[htb]
  \centering
  \begin{minipage}[l]{.4\textwidth}
  \centering
  \psfrag{a}[cb][cb]{$a$}
  \psfrag{b}[cb][cb]{$b$}
  \psfrag{c}[cb][cb]{$c$}
  \includegraphics[scale=0.35]{figures/tree1.ps}
  \caption{Leaf $c$ is not allowed to lie between $a$ and $b$.}
  \label{fig:intra_cross}
  \end{minipage}
  \qquad
  \begin{minipage}[r]{.4\textwidth}
  \centering
  \psfrag{u}[cb][cb]{$a$}
  \psfrag{v}[cb][cb]{$b$}
  \psfrag{w}[cb][cb]{$c$}
  \psfrag{z}[cb][cb]{$d$}
  \psfrag{r}[cb][cb]{$r$}
  \includegraphics[scale=0.35]{figures/tree2.ps}
  %\includegraphics[width=4.75cm]{figures/tree2.ps}
  \caption{Variables~$x_{ac}$ and~$x_{bd}$ can be identified.}
  \label{fig:intra_cross2}
  \end{minipage}
\end{figure}

Therefore, we derive a betweenness restriction for every triple of
leaves such that two of the leaf pairs have different lowest common
ancestors. Each restriction of the form `$c$ cannot be placed between
$a$ and $b$' can be written as $x_{ac}x_{cb}=0$ and $x_{bc}x_{ca}=0$,
i.e., $y_{accb}=0\;\textnormal{ and }\;y_{cabc}=0$.
As mentioned above, the polytope corresponding to (LQLO) is isomorphic
to a face of a cut polytope~\cite{bwz07}.  Since all $y$-variables are
binary, the additional betweenness constraints are always
face-inducing for (LQLO).  \enlargethispage{0.35cm}
\begin{thm}\label{th:cutpolytope}
  The problem of drawing tanglegrams with a minimum number of edge
  crossings can be solved by optimizing over a face of a suitable cut
  polytope.
\end{thm}

\section{Results}\label{sec:results}

We implemented the above model. The naive approach is to solve the
linearized model (LQLO) using a standard integer programming solver. A
more advanced approach is to solve the quadratic reformulation
\eqref{eq:qlofaces}, using separation of cutting planes for max-cut,
both in the context of integer and semidefinite programming.  For the
IP-based methods, we used CPLEX~11.2, whereas for the SDP approaches,
we used the bundle method by
 \cite{RRW07}.
For random and real-world binary as well as general trees with low
tangle density, the SDP approach usually needs considerably more time
than the IP-based methods. Furthermore, memory requirements strongly
increase with system size. On average, the fastest approaches are the
pure standard linearization \emph{IP} and the quadratic reformulation
\emph{QP}. In fact, we can optimize tanglegrams with more than~500
leaves in each tree which is the range of real-world instance sizes.
For big enough tangle density the SDP approach usually outperforms the
IP approaches. Memory requirements, however, usually prohibit solving
binary instances with more than 500 leaf nodes and tangle density of
$1\%$. For general trees, best performance is often found for the
quadratic reformulation. These non-binary instances could
not be solved before by any other exact method.

\begin{thebibliography}{00}

% \bibitem{label}
% Text of bibliographic item

% notes:
% \bibitem{label} \note

% subbibitems:
% \begin{subbibitems}{label}
% \bibitem{label1}
% \bibitem{label2}
% If there is a note, it should come last:
% \bibitem{label3} \note
% \end{subbibitems}

\bibitem{bwz07} C. Buchheim and A. Wiegele, and L. Zheng. Exact
  Algorithms for the Quadratic Linear Ordering Problem. 
\textit{INFORMS Journal on Computing}. To appear.

\bibitem{S88} C. De Simone. The Cut Polytope and the Boolean Quadric Polytope.
  \textit{Discrete Mathematics}, 79; 71--75, 1989.

\bibitem{EW94} P. Eades and N. C. Wormald. Edge crossings in drawing
  bipartite graphs. \textit{Algorithmica}, 11; 379--403, 1994.

\bibitem{fkp09} H. Fernau and M. Kaufmann, and M. Poths. Comparing
  trees via crossing minimization. \textit{Journal of Computer and System Sciences}.
  In Press.

\bibitem{nhvw08} M. N{\"o}llenburg, M. V{\"o}lker, A. Wolff, and
               D. Holten. Drawing Binary Tanglegrams: An Experimental Evaluation.
 In \textit{Proc.\ of the Workshop on Algorithm Engineering and
               Experiments, ALENEX 2009}, pages 106-119, SIAM, 2009.

\bibitem{RRW07} F. Rendl, G. Rinaldi, and A. Wiegele. A Branch and
  Bound Algorithm for Max-Cut Based on Combining Semidefinite and
  Polyhedral Relaxations. In M. Fischetti and D. P. Williamson,
  editors, \textit{IPCO~2007}, volume 4513 of \textit{Lecture Notes in
    Computer Science}, pages 295-309. Springer, 2007.

\bibitem{vasg09} B. Venkatachalam, J. Apple, K. St. John, and
  D. Gusfield. Untangling Tanglegrams: Comparing Trees by Their Drawings.
    \textit{Bioinformatics Research and Applications},
    pages 88--99, 2009.

\end{thebibliography}

\end{document}

