# Solving the Persistent Phylogeny Problem in polynomial time

Paola Bonizzoni Dipartimento di Informatica Sistemistica e Comunicazione,
Univ. degli Studi di Milano–Bicocca<EMAIL_ADDRESS>Gianluca Della Vedova∗ Gabriella Trucco Dipartimento di Tecnologie
dell’Informazione, Univ. degli Studi di Milano, Crema.
<EMAIL_ADDRESS>
(November 2nd, 2016)

###### Abstract

The notion of a Persistent Phylogeny generalizes the well-known Perfect
phylogeny model that has been thoroughly investigated and is used to explain a
wide range of evolutionary phenomena. More precisely, while the Perfect
Phylogeny model allows each character to be acquired once in the entire
evolutionary history while character losses are not allowed, the Persistent
Phylogeny model allows each character to be both acquired and lost exactly
once in the evolutionary history. The Persistent Phylogeny Problem (PPP) is
the problem of reconstructing a Persistent phylogeny tree, if it exists, from
a binary matrix where the rows represent the species (or the individuals)
studied and the columns represent the characters that each species can have.

While the Perfect Phylogeny has a linear-time algorithm, the computational
complexity of PPP has been posed, albeit in an equivalent formulation, 20
years ago. We settle the question by providing a polynomial time algorithm for
the Persistent Phylogeny problem.

##  1 Introduction

The problem of reconstructing an evolutionary history from characters is a
classical topic in computational biology [29, 30]. The instance of the problem
consists of a matrix $M$ where the rows corresponds to species (or
individuals/taxa) and columns corresponds to characters. Moreover, each entry
$M[s,c]$ is the _state_ of species $s$ and character $c$. Notice that each
character can be phenotypical (i.e., a species has wings) or genotypical (a
cell has a certain mutation). A _phylogeny_ is a tree $T$ where each input
species is a node, a character $c$ can be gained or lost in each edge of $T$:
how a character can be gained or lost in the tree $T$ is called the evolution
model.

There is a contrast between different evolution models, as more restrictive
models — such as the Perfect Phylogeny — are more informative, but are unable
to give a tree consistent with all possible input matrices. On the other hand,
more general models, such as Camin-Sokal [10] and Dollo [27] are always able
to produce a tree consistent with the input matrix, but such tree might not be
informative on the actual evolutionary history.

In this paper we will focus on binary characters, that is the state $0$ means
that a species does not have a character, while the state $1$ means that a
species has a character. Each edge represents a change of state for some
characters during the evolution of the ancestral taxa: a change from $0$ to
$1$ is the gain of a character, while a change from $1$ to $0$ is the loss of
a character. Two main general models have been introduced in the literature to
describe character-based evolutions of taxa: the Camin-Sokal [10] and the
Dollo [27] model.

The Camin-Sokal model assumes that each character may change state from $0$ to
$1$ several times, but no change from $1$ to $0$ state is allowed.
Differently, in the Dollo model, characters may change state from $0$ to $1$
only once in the tree, but they may change state from $1$ to $0$ multiple
times. The Dollo model appears appropriate for reconstructing the evolution of
genes in eukaryotic organisms, mainly the gain and loss of genes modeled as
change to $1$ and to $0$ respectively in the taxa. Indeed, while multiple
gains of the same gene in different lineages is improbable, multiple losses of
a gene are more common [27]. The model recently gained a lot if interest in
the context of reconstructing the clonal evolution in tumors due to mutation
events taking into account copy number aberrations [23]. In this context
characters are mutations that are gained or lost during the clonal evolution.
It is assumed that a given mutation is acquired at most once in the tree, but
it may be lost due to the loss of genes related to deletion events.

From the algorithmic point of view, the Dollo model has a trivial decision
problem — given a matrix $M$, there is always a tree $T$ consistent with $M$ —
and an NP-complete optimization problem — find a tree $T$ consistent with $M$
and minimizing the number of changes of state.

At the other end of the spectrum lies the Perfect Phylogeny Problem [18] which
is likely the most restrictive possible model: each character is acquired
exactly once in the tree $T$ and is never lost. Despite its relative
simplicity, the Perfect Phylogeny model has found several applications in
Biology [2, 12, 13, 14] and Linguistics [26]. Moreover the Perfect Phylogeny
has been extensively studied from a computational point of view, starting from
the seminal linear-time algorithm [17] for binary matrices, and going on with
the NP-completeness for the general case of unbounded number of states [4],
and the polynomial-time algorithms for any constant number of states [1, 20].
Moreover, the algorithmic properties of some variants of the Perfect Phylogeny
have been recently studied [22, 21, 3] restricting the possible state
transitions or the topology of the tree. Another result that is especially
relevant for our paper is a polynomial-time algorithm for computing the
Directed Perfect Phylogeny with Missing Data [24], where a first reframing of
Perfect Phylogeny as a graph problem.

Still, some biological problems require a more general model than the Perfect
Phylogeny model, but need an efficient algorithm to compute an informative
tree [15]. In this direction, the notion of a _persistent_ character have been
proposed in [25] and later studied [5, 6, 7, 8]: a persistent character can
change state from $0$ to $1$ at most once during the evolution then change
state from one to zero, again at most once in the entire tree. The
computational problem of constructing a persistent phylogeny, albeit in a
different context, has been introduced at least as early as 1996 [16], where
it takes the name of $(1,2)$-phylogeny and the open problem of determining its
computational complexity has been stated.

Recently some algorithms for the PPP have been introduced: more precisely, an
algorithm whose time complexity is polynomial in the number of taxa, but
exponential in the number of characters [5], and an integer linear programming
solution [19]. The ILP formulation uses a reformulation of the PPP as the
problem of completing a matrix $M_{e}$ obtained by doubling columns of the
input matrix $M$ of the PPP problem (i.e. adding a persistent copy of the
character) and posing as unknown the state of characters that may be
persistent — those characters that have entry $0$ in matrix $M$. In [5, 7] the
PPP problem is restated as a colored graph problem. In this paper we use this
graph framework to design a polynomial time algorithm that solves the PPP
problem, settling the question of [16]. An implementation of our algorithm is
available at http://www.algolab.eu/persistent-phylogeny.

##  2 Preliminaries

The input of the PPP problem is an $n\times m$ binary matrix $M$ whose columns
are associated with the set $C=\\{c_{1},\ldots,c_{m}\\}$ of characters and
whose rows are associated with the set $S=\\{s_{1},\dots,s_{n}\\}$ of taxa
also called _species_ in the paper. Then $M[s,c]=1$ if and only if the species
$s$ has character $c$, otherwise $M[s,c]=0$.

The character $c$ is _gained_ in the only edge where its state goes from $0$
to $1$ or, more formally, in the edge $(x,y)$ such that $y$ is a child of $x$
and $c$ has state $0$ in $x$ and state $1$ in $y$. In this case the edge
$(x,y)$ is labeled by $c^{+}$. Conversely, $c$ is _lost_ in the edge $(x,y)$
if $y$ is a child of $x$ and character $c$ has state $1$ in $x$ and state $0$
in $y$. In the latter case the edge $(x,y)$ is labeled by $c^{-}$. For each
character $c$, we allow at most one edge labeled by $c^{-}$ [31, 5]. Each
character $c^{+}$ and $d^{-}$ is called a _signed_ character.

Let $c$ be an unsigned character and let $M$ be an instance of the PPP
problem. Then $S(c)$ is the set of species that have the character $c$, that
is the set $\\{s\in S:M[s,c]=1\\}$. Given two characters $c_{1}$ and $c_{2}$,
we will say that $c_{1}$ _includes_ $c_{2}$ if $S(c_{1})\supseteq S(c_{2})$.
Then a character $c$ of $M$ is _maximal in $M$_ if $S(c)\not\subset
S(c^{\prime})$ for any character $c^{\prime}$ of $M$. Moreover two characters
$c,c^{\prime}$ _overlap_ if they share a common species but neither is
included in the other. We now introduce the definition of Persistent Phylogeny
used in the paper [7].

######  Definition 1 (Persistent Phylogeny).

Let $M$ be an $n\times m$ binary matrix over a set $m$ of characters and a set
$n$ of species. Let $A$ be a subset of its characters, called _active_
characters. Then a _persistent phylogeny_ , in short _p-pp_ , for the pair
$(M,A)$ is a rooted tree $T$ such that:

  1. 1.

each node $x$ of $T$ is labeled by a vector $l_{x}\in\\{0,1\\}$ of length $m$;

  2. 2.

the root $r$ of $T$ is labeled by a vector $l_{r}$ such that $l_{r}(j)=1$ if
and only if $c_{j}\in A$, while for each node $x$ of $T$ the value
$l_{x}[j]\in\\{0,1\\}$ represents the state of character $c_{j}$ in the node
$x$;

  3. 3.

each edge $e=(v,w)$ is labeled by a character,

  4. 4.

for each character $c_{j}$ there are at most two edges $e=(x,y)$ and
$e^{\prime}=(u,v)$ such that $l_{x}[j]\neq l_{y}[j]$ and $l_{u}[j]\neq
l_{v}[j]$ (representing a change in the state of $c_{j}$). In that case $e$,
$e^{\prime}$ occur along the same path from the root of $T$ to a leaf of $T$;
if $e$ is closer to the root than $e^{\prime}$, then $l_{x}[j]=l_{v}[j]=0$,
$l_{y}[j]=l_{u}[j]=1$, and the edge $e$ is labeled $c_{j}^{+}$, while
$e^{\prime}$ is labeled $c_{j}^{-}$;

  5. 5.

for each row $x$ of $M$ there exists a node $x$ of $T$ labeled by row $x$ and
such that vector $l_{x}$ is equal to the row $x$.

Set $A$ is also called _active set_ of matrix $M$ and we say that the matrix
$M$ is solved by tree $T$.

Observe that the definition of persistent phylogeny allows the internal nodes
of $T$ to be labeled by species. The definition given in [5] corresponds to
the case the set $A$ is empty, i.e. the root of a tree $T$ is labeled by the
length $m$ zero vector.

The above generalization allows to consider persistent phylogenies where the
root state is not the zero vector. This fact is relevant when considering
subtrees of the phylogenies as solutions of the same problem on subinstances
of the input. Indeed, notice that subtrees of the tree solving the instance
$M$ have roots that are not labeled by the zero vector.

If there exists an edge of $T$ labeled $c^{-}$, then then the character $c$ is
called _persistent_ in $T$. Moreover, for each character $c\in A$ only the
edge labeled $c^{-}$ might appear in the phylogeny.

A special case, called _perfect phylogeny_ , is when no character of $T$ is
ever lost.

######  Definition 2 (Perfect Phylogeny).

A persistent phylogeny $T$ is a _perfect_ phylogeny if there are no persistent
characters in tree $T$.

Since no two edges share the same label of $T$, we might use the label to
identify and denote an edge.

Given a tree $T$ and a node $x$, we say that a character $c$ occurs below node
$x$ if $c$ labels an edge of a path from node $x$ to a leaf node of tree $T$.
Similarly, we say that a node $v$ occurs below node $x$ if $v$ is along a path
from node $x$ to a leaf of tree $T$. Moreover, we will say that the character
$c$ is _above_ the node $x$ if there is an edge of the path from $x$ to the
root that is labeled by $c$.

###  2.1 The red-black graph and conflicting characters

In this paper, our algorithm is based on a graph called the _red-black graph_
and denoted by $G_{RB}$. Red-black graphs provide an equivalent representation
of matrices that are solved by persistent phylogenies [5, 7]. Moreover, the
iterative construction or visit of a tree can be restated as applying specific
graph operations to the red-black graph. In this section we recall the main
results that we use in our algorithm. A connected component is called
_nontrivial_ if it has more than one vertex.

$M$ | $c_{1}$ | $c_{2}$ | $c_{3}$ | $c_{4}$ | $c_{5}$ | $c_{6}$ | $c_{7}$ | $c_{8}$
---|---|---|---|---|---|---|---|---
$s_{1}$ | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1
$s_{2}$ | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0
$s_{3}$ | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0
$s_{4}$ | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0
$s_{5}$ | 1 | 1 | 1 | 0 | 1 | 0 | 1 | 0
$s_{6}$ | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0
Figure 1: Instance of the Persistent Persistent Phylogeny problem where the
set of active characters is $A=\\{c_{4}\\}$. Figure 2: Red-black graph
associated with the matrix in Figure 1 and with set $A=\\{c_{4}\\}$ of active
characters.

######  Definition 3 (Red-black graph).

A _red-black graph_ on a set $S$ of species and a set $C$ of characters,
denoted by $G_{RB}$, is a bipartite graph whose vertex set is $S\cup C$.

Moreover each character $c\in C$ is incident only on black edges (in this case
$c$ is _inactive_), or it is incident only on red edges (in this case $c$ is
_active_).

Given $A$ an empty set of active characters and $M$ an instance of PPP, the
red-black _associated with $M$_ is the graph $G_{RB}=(S\cup C,E)$ that has
black edges given by set $E=\\{(s,c):s\in S,c\in C,M[s,c]=1\\}$.

Conversely, given a red-black graph, the following definition of a matrix
associated with a red-black graph justifies our use of red-black graphs in
place of binary matrices.

Given a red-black graph $G_{RB}=(S\cup C,E)$, the matrix $M$ _associated with
$G_{RB}$_ has species $S$ and characters $C$ and active set $A$ given by the
characters in $C$ with incident red edges. Moreover $M[s,c]=1$ iff (1) $(s,c)$
is a black edge of $G_{RB}$, or (2) $c$ is active and $(s,c)$ is not an edge
of $G_{RB}$.

In this paper we use extensively the following notion.

######  Definition 4 (Persistent phylogeny for $G_{RB}$).

Let $G_{RB}$ be a red-black graph with active characters $A$. Let $M$ be the
matrix associated with $G_{RB}$. Then the persistent phylogeny for $G_{RB}$ is
the persistent phylogeny for the pair $(M,A)$.

If $T$ is a persistent phylogeny for $G_{RB}$ we also say that $G_{RB}$ is
solved by tree $T$. We recall that, given a vertex $v$ of a graph $G$, the
_neighborhood_ of $v$ is the set of vertices of $G$ that are adjacent to $v$,
and it is denoted by $N(v)$ [11]. In a previous paper [7] it has been proved
that given a persistent phylogeny $T$ solving red-black graph $G_{RB}$, then
$T$ can be related to a sequence of graph operations on graph $G_{RB}$ which
are described in the following definition.

######  Definition 5 (Realization).

Let $G_{RB}$ be a red-black graph, and let $c$ be a character of $G_{RB}$. Let
$D(c)$ be the set of species in the connected component of $G_{RB}$ that
contains $c$. The result of the _realization of $c^{+}$ on $G_{RB}$_, which is
defined only if $c$ is inactive, is a red-black graph obtained from $G_{RB}$
by adding a red edge between $c$ and each species in $D(c)\setminus N(c)$,
deleting all black edges incident on $c$, and finally deleting all isolated
vertices. The _realization of $c^{-}$ on $G_{RB}$_ is defined only if $c$ is
active and there is no species in $D(c)\setminus N(c)$: in this case the
results of the realization is obtained from $G_{RB}$ by deleting all edges
incident on $c$, and then deleting all isolated vertices.

The realization of a species $s$ is the realization of its set $C(s)$ of
characters in any order. An active character $c$ that is connected to all
species of a graph $G_{RB}$ by red edges is called _free_ in $G_{RB}$ and it
is then deleted from $G_{RB}$.

The main relationship between a graph $G_{RB}$ and the tree solving $G_{RB}$
is given by the notion of _c-reduction_ stated in [5]. A c-reduction $R$ is a
sequence of positive characters. A c-reduction $R$ is _feasible_ for $G_{RB}$
if the realization of each character in the sequence $R$ one after the other
is defined and the realization of a negative character $c^{-}$ must be applied
whenever $c^{-}$ is free in $G_{RB}$.

Clearly a c-reduction also represents a sequence of graph operations on
$G_{RB}$. Then the _application_ of a feasible c-reduction $R=\langle
c_{1}^{+},\ldots,c_{k}^{+}\rangle$ to red-black graph $G_{RB}$ is the graph
$G_{RB}^{k}$ obtained as follows: $G_{RB}^{0}$ is the red-black graph
$G_{RB}$, while, when $i>0$, $G_{RB}^{i}$ is obtained from $G_{RB}^{i-1}$ by
realizing the character $c_{i}^{+}$ and, eventually all previous characters
${c_{l}}^{-}$, for $1\leq l<i$ such that $c_{l}$ is free after the realization
of $c_{i}$. Then the _extended_ c-reduction of $R$ [7] is the sequence of
positive and negative characters obtained by the application of $R$ to
$G_{RB}$. For example, the c-reduction $\langle
c_{3}^{+},c_{5}^{+},c_{2}^{+}\rangle$ corresponds to the extended c-reduction
$\langle c_{3}^{+},c_{5}^{+},c_{2}^{+},c_{4}^{-}\rangle$, since the character
$c_{4}$ becomes free after the realization of $c_{2}^{+}$ (see Figure 6 for
the corresponding red-black graph).

The following fact that we use in the paper is stated and proved in [7]. A
_tree traversal_ of $T$ is a sequence of the nodes of $T$ where each node
appears exactly once [28] and has the additional properties that a node always
precedes all of its descendants.

######  Proposition 6 (Successful reduction).

A tree traversal of the positive characters of a tree $T$ solving a graph
$G_{RB}$ is a c-reduction $R$ that is feasible for $G_{RB}$ and its
application to $G_{RB}$ results in an empty graph. Then $R$ is called a
_successful reduction_ for $G_{RB}$.

In [7] it has been proved that given a red-black graph $G_{RB}$ and a
successful reduction $R$, there exists a polynomial time algorithm that
computes a persistent phylogeny solving $G_{RB}$.

Based on Proposition 6 we observe that a successful reduction for a red-black
graph $G_{RB}$ can be characterized using the notion of red $\Sigma$-graph:
this is a path of length four induced in $G_{RB}$ by a pair $c_{1}$ and
$c_{2}$ of active characters and by three species $s_{1}$ and $s_{2}$ and
$s_{3}$. Observe that $c_{1}$ and $c_{2}$ cannot be free in the red-black
graph as they cannot be connected to all species of the red-black graph by red
edges and thus ${c_{1}}^{-}$ and ${c_{2}}^{-}$ cannot be realized.
Consequently, a red-black graph containing a red $\Sigma$-graph cannot be
reduced to an empty graph by a c-reduction.

Now, the notion of conflicting characters is used to detect candidate pairs of
characters that may induce a red $\Sigma$-graph. Let $M$ be a binary matrix
and let $c_{1}$, $c_{2}$ be two characters of $M$. Then the configurations
induced by the pair $(c_{1},c_{2})$ in $M$ is the set of ordered pairs
$(M[s,c_{1}],M[s,c_{2}])$ over all species. Two characters $c_{1}$ and $c_{2}$
of $M$ are _conflicting_ if and only if the configurations induced by such
pair of columns is the set of all possible pairs $(0,1)$, $(1,1)$, $(1,0)$ and
$(0,0)$.

We say that characters $c,c^{\prime}$ in graph $G_{RB}$ are _conflicting_ if
they are conflicting in the matrix associated with $G_{RB}$. Then graph
$G_{RB}$ contains a conflict if it has a conflicting pair of characters.

The following two main observations [5, 7] and Lemma 9 will be used in the
next sections and are crucial in the polynomial time algorithm for computing a
successful reduction for the red-black graph.

######  Observation 7.

A c-reduction $R$ for graph $G_{RB}$ is successful if and only if $R$ includes
all characters of the graph and each graph ${G_{RB}}_{i}$ obtained after the
realization of the first $i$-characters of sequence of $R$ does not contain
red $\Sigma$-graphs.

Another important observation used in the paper and easy to prove by the
definition of realization of a character is the following.

######  Observation 8.

A red-black graph consisting of $k$ distinct components has a successful
reduction $R$ if and only if each component ${G_{RB}}_{i}$ has a successful
reduction $R_{i}$. Then $R$ consists of any concatenation of the $k$ sequences
$R_{i}$.

######  Lemma 9.

Let $G_{RB}$ be a red-black graph solved by $T$. If $G_{RB}$ is connected then
the root $r$ of $T$ has only one child.

We will assume that the instances of the PPP problem do not contain any free,
null or universal characters (a null character is an isolated vertex of the
red-black graph, while a universal character is adjacent to all species of the
red-black graph by black edges -), or a null species (a species that possesses
no characters). Notice that the removal of null characters does not modify the
phylogeny, while a null species can only be associated to the root of the
phylogeny. Removing a universal character trivially consists of fixing the
first character of a c-reduction or, equivalently, determining the label of a
topmost edge of the phylogeny. Moreover, we will assume that the instances of
the PPP problem do not have two identical columns.

A _reducible_ red-black graph $G_{RB}$ is an instance of the PPP problem that
admits a successful reduction, i.e. it is solved by a persistent phylogeny,
and $G_{RB}$ is a connected graph.

###  2.2 Maximal reducible graphs

The red-black graph _induced in $G_{RB}$ by a set $C^{\prime}$ of characters_,
denoted as $G_{RB}|C^{\prime}$, consists of the subgraph $G_{RB}^{\prime}$ of
$G_{RB}$ induced by the set all characters in $C^{\prime}$ and the species of
$G_{RB}$ that are adjacent to $C^{\prime}$.

Given a red-black graph $G_{RB}$ and its associated matrix $M$, then a
character $c$ of $G_{RB}$ is _maximal_ in $G_{RB}$ if it is maximal among the
inactive characters of $M$. Then we denote by $C_{M}$ the set of maximal
characters for a red-black graph $G_{RB}$.

A _maximal reducible_ graph consists of a reducible red-black graph whose
characters are all maximal and inactive in the graph. Then $G_{RB}|C_{M}$ is
the maximal reducible graph induced by $C_{M}$ in graph $G_{RB}$. In the paper
we denote by $G_{M}$ a maximal reducible graph and by $T_{M}$ a tree solving a
maximal reducible graph.

Given a tree $T$, a path $\pi$ of the tree is _simple_ if it consists of
internal nodes of outdegree and indegree one.

###  2.3 The Hasse diagram

Our polynomial time algorithm for solving the PPP problem computes a
successful reduction of a red-black graph $G_{RB}$ associated to the input
matrix $M$ in polynomial time, if it exists. Then the algorithm in [7] can be
used to build a tree $T$ from the successful reduction. The computation of a
successful reduction for $G_{RB}$ is done by computing the Hasse diagram
$\mathcal{P}$ of its maximal reducible graph $G_{M}$ obtained as the
restriction $G_{RB}|C_{M}$, where $C_{M}$ is the set of maximal characters of
$G_{RB}$. In the following, given $s$ a species, by $C(s)$ we denote the set
of characters of $s$.

######  Definition 10 (Hasse diagram for a maximal reducible graph).

Let $G_{M}$ be a maximal reducible graph. Then the diagram $\mathcal{P}$ for
$G_{M}$ is the Hasse diagram for the poset $(P_{s},\leq)$ of all species of
$G_{M}$ ordered by the relation $\leq$, where $s_{1}\leq s_{2}$ if
$C(s_{1})\subseteq C(s_{2})$.

Given $(P_{s},\leq)$ the poset of all inactive species of a red-black, we
consider the representation of the poset $(P_{s},\leq)$ by its Hasse diagram
(or simply diagram), represented by a directed acyclic graph $\cal P$ [9].
More precisely, two species $s_{1}$ and $s_{2}$ are connected by the arc
$(s_{1},s_{2})$ if $s_{1}<s_{2}$ and there does not exist a species $s_{3}$
such that $s_{1}<s_{3}<s_{2}$. The definition of $\cal P$ can be immediately
translated into a polynomial time construction algorithm [9]. The main notions
that we use in the following related to a diagram $\mathcal{P}$ are those of
_source_ , _sink_ and _chain_. A _source_ is a node of indegree $0$ and a
_sink_ a node of out-degree $0$. In particular, a _chain_ of $\mathcal{P}$ is
a direct path of $\mathcal{P}$ from a source to a sink of $\mathcal{P}$.
Observe that each edge $(s_{i},s_{i+1})$ of diagram $\mathcal{P}$ is labeled
by the set of positive characters that are in $C(s_{i+1})$ and not in
$C(s_{i})$. A chain is _trivial_ if it consists of a singleton in the diagram.
Thus a diagram $\mathcal{P}$ consisting only of trivial chains is called
_degenerate_. Given a chain $\mathcal{C}$ of the diagram $\mathcal{P}$ for a
graph $G_{M}$, we associate to it a c-reduction.

######  Definition 11 (c-reduction of a chain).

The c-reduction of the chain $\mathcal{C}=<s_{1},s_{2},\ldots,s_{k}>$ of the
diagram $\mathcal{P}$ for a graph $G_{M}$ is the sequence of characters of
$s_{1}$ and those labeling the arcs $(s_{i},s_{i+1})$ for $1\leq i\leq k-1$.

The following two notions of _safe chain_ and _safe source_ are crucial for
building our algorithm. Observe that the notion of safe chain is related to a
maximal reducible graph $G_{RB}|C_{M}$ while the notion of safe source is
related to a reducible graph $G_{RB}$. Some examples are in the Appendix as
Figures 7 and 8.

######  Definition 12 (safe chain).

Let $G_{M}$ be a maximal reducible red-black graph, let $\mathcal{P}$ be the
diagram for $G_{M}$, and let $\mathcal{C}$ be a chain of $\mathcal{P}$. Then
$\mathcal{C}$ is _safe_ if the c-reduction $S(\cal C)$ of $\mathcal{C}$ is
feasible for the graph $G_{M}$ and applying $S(\cal C)$ to $G_{M}$ results in
a graph that has no red $\Sigma$-graph.

######  Definition 13 (safe source).

Let $G_{RB}$ be a red-black graph, let $\mathcal{P}$ be the diagram for
$G_{RB}|C_{M}$. A source $s$ of a chain $\mathcal{C}$ of diagram $\mathcal{P}$
is _safe for $G_{RB}$_ if the realization of $s$ in $G_{RB}$ does not induce
red $\Sigma$-graphs in $G_{RB}$.

###  2.4 The algorithm

The polynomial time algorithm for finding a successful reduction of a graph
$G_{RB}$ starts with the detection in the graph of universal or free
characters, which must be realized as the first characters in the graph.

Then the algorithm applies observation 8: if $G_{RB}$ is disconnected then we
decompose a red-black graph into its connected components, solve recursively
each component separately, and finally concatenate all successful reduction
computed. Therefore we focus only on instances corresponding to connected red-
black graphs.

By Lemma 9 any tree $T$ solving a connected $G_{RB}$ has a unique child of the
root $r$. Moreover a direct consequence of the definition of maximal character
in $G_{RB}$ is that the edge incident to $r$ is labeled by at least a maximal
character.

Clearly, given $C_{M}$ the set of maximal characters of $G_{RB}$, the tree $T$
contains a solution $T_{M}$ for the subgraph $G_{RB}|C_{M}$ where $T_{M}$ is
obtained from $T$ by contracting all edges that are not labeled by characters
in $C_{M}$. The first main results of our paper is that the tree $T_{M}$ has a
very specific topology that is strictly related to the one of all other
possible solutions for $G_{RB}|C_{M}$ and this form is computed from the Hasse
diagram $\mathcal{P}$ for $G_{RB}|C_{M}$. More precisely, if $\mathcal{P}$ is
not degenerate then there are at most two trees $T_{1},T_{2}$ solving
$G_{RB}|C_{M}$: in this case $T_{2}$ is obtained from $T_{1}$ by reversing a
path form an internal node to a leaf of $T_{1}$. If $\mathcal{P}$ is
degenerate, then there can be multiple solutions for $G_{RB}|C_{M}$, but again
given two trees $T_{1},T_{2}$ solving $G_{RB}|C_{M}$, $T_{2}$ is obtained from
$T_{1}$ by reversing a path form an internal node to a leaf of $T_{1}$.

Now, using the Hasse diagram, we can compute in polynomial time for each tree
$T_{M}$ solving $G_{RB}|C_{M}$ the maximal characters that label the longest
path of $T_{M}$ that starts from the root and is labeled by positive
characters: such path is given by a safe chain of diagram $\mathcal{P}$. If
the diagram $\mathcal{P}$ has multiple safe chains, we are able to choose in
polynomial time the correct chain, i.e. the correct tree $T_{M}$, by testing
the source of the chain using $G_{RB}$: this is given by the notion of safe
source (Definition 13) stated before. More precisely, a tree $T$ solving
$G_{RB}$, and equivalently a successful reduction of $G_{RB}$, starts with the
sequence of maximal characters of a safe source of the diagram $\mathcal{P}$.

The above observations are applied in the following two main steps of the
algorithm used for computing a successful reduction of a reducible red-black
graph $G_{RB}$.

Step 1: compute the Hasse diagram $\mathcal{P}$ for the maximal reducible
graph $G_{RB}|C_{M}$. Then find a safe source $s$ of $\mathcal{P}$. Theorems
28 and 27 show that there exists a tree $T$ for $G_{RB}$ that starts with the
characters of $s$.

Step 2: update graph $G_{RB}$ with the realization of the characters of the
safe source $s$. By Theorem 29 the updated graph $G_{RB}$ is still reducible
and the algorithm is then applied recursively on $G_{RB}$.

Finally, observe that the correctness of the algorithm is based on the above
theorems stating characterizations of trees solving maximal reducible graphs
and reducible graphs. Whenever the input of the algorithm is a non reducible
graph, the above two steps fail.

The rest of the paper presents the arguments that Algorithm 1 (Reduce) that
computes a successful reduction of a reducible graph.

##  3 Maximal reducible graphs

In this section we consider only maximal reducible graphs and give a
characterization of the trees solving such graphs. Observe that we assume that
a simple path in a tree $T$ between two species may be contracted to a unique
edge that is labeled by the sequence of characters occurring along the path.
We distinguish three types of edges in a tree: _positive edges_ that are only
labeled by positive characters, _negative edges_ that are only labeled by
negated characters and _mixed_ ones, where both positive and negative
characters occur.

In the paper we consider two main types of trees representing the persistent
phylogenies solving maximal reducible graphs: line-trees and branch-trees. A
tree $T$ is a line-tree if it consists of a simple path. A tree $T$ is a
branch-tree if it consists of a simple path from the root $r$ to a node $x$
that is the topmost node with more than one child, and no positive character
occurs below node $x$: in this case the path from $r$ to node $x$ is called
the initial-path of the tree $T$, and the node $x$ is called the branch-node
of $T$.

######  Lemma 14.

Let $G_{M}$ be a maximal reducible graph and let $T_{M}$ be a solution of
graph $G_{M}$. Then $T_{M}$ is either a line-tree or a branch-tree.

###### Proof.

Let $T_{M}$ be any solution of $G_{M}$ and let $x$ be the topmost node of tree
$T$ that has at least two children. If $x$ does not exist, then $T$ is a line-
tree, and thus the Lemma holds. By Lemma 9, $x$ is not the root, hence in the
initial path there is an edge labeled by a positive character. In fact, if the
first character of tree $T_{M}$ is a negated character, it means that $G_{M}$
has an active character connected to all species of $G_{RB}$ which is not
possible as the graph $G_{RB}$ is reduced. Assume that below $x$ there exists
an edge labeled $d^{+}$. Since graph $G_{M}$ is connected, there must exist a
positive character $a^{+}$ in the initial path of tree $T_{M}$ such that is
negated below the node $x$. Indeed, if all characters are negated before node
$x$, it must be that all positive characters below node $x$ are disjoint from
the other characters of the initial path which contradicts the assumption that
the graph $G_{M}$ is connected.

Assume that $a^{-}$ occurs along a branch distinct from the one having
character $d^{+}$. Then $a$ is greater than $d$ and this contradicts the
assumption that $d$ is a maximal character, i.e. all characters of $T_{M}$ are
maximal in $G_{M}$. Indeed, observe that all species having $d$ have also
character $a$. Otherwise, assume that $a^{-}$ and $d^{+}$ occur along the same
branch of tree $T_{M}$.

Then let us consider the edge $e$ outgoing from $x$ that is not in the same
branch as $d^{+}$. If such edge $e$ is labeled by a positive edge $b^{+}$,
then $b$ is smaller than $a$ and is not maximal, which contradicts the initial
assumption that characters are maximal ones. Indeed, $a^{-}$ occurs along a
branch distinct from the one having $b^{+}$ and thus all species with $b$ have
also have character $a$. Otherwise edge $e$ is labeled by character $b^{-}$.
But then $b$ is greater than $d$, contradicting the assumption that all
characters are maximal. Indeed, observe that all species including character
$d$ have also character $b$. ∎

Given a line-tree $T_{1}$ whose sequence of species of a depth-first traversal
is $s_{1},\ldots,s_{k}$, the inverted tree $T_{2}$ has the sequence of species
$s_{k},\ldots,s_{1}$. Moreover, the label of each edge $(s_{i+1},s_{i})$ in
$T_{2}$ has the same characters as the edge $(s_{i},s_{i+1})$ in $T_{1}$, but
with opposite signs (positive characters in $T_{1}$ are negative characters in
$T_{2}$ and vice versa).

######  Lemma 15.

Let $G_{M}$ be a maximal reducible graph solved by a line-tree $T_{M}$. Then
the line-tree $T_{1}$ obtained from $T_{M}$ inverting the entire tree is a
solution for $G_{M}$.

###### Proof.

It is an immediate consequence of the observation that $T_{M}$ has no active
character, by our definition of maximal reducible graph. ∎

######  Lemma 16.

Let $G_{M}$ be a maximal reducible graph, let $T_{M}$ be a solution of
$G_{M}$, and let $c,c^{\prime}$ be overlapping characters occurring in tree
$T_{M}$ and inactive in $G_{M}$. Then one of the following cases hold:

  * •

$T_{M}$ contains the sequence of edges $c^{+}$ $c^{\prime+}$, $c^{-}$,
$c^{\prime-}$, with $c^{\prime-}$ eventually missing;

  * •

$T_{M}$ contains the sequence of edges $c^{\prime+}$ $c^{+}$, $c^{\prime-}$,
$c^{-}$, with $c^{-}$ eventually missing;

  * •

$c^{-}$ and $c^{\prime-}$ appear in two distinct paths, and $T_{M}$ has a
species preceding both $c^{+}$ and $c^{\prime+}$ if they are conflicting in
$G_{M}$.

###### Proof.

Since $c$ and $c^{\prime}$ are maximal characters, if all four edges $c^{+}$,
$c^{\prime+}$, $c^{-}$, $c^{\prime-}$ appear in the same path, the relative
order of $c^{+}$ and $c^{\prime+}$ must be the same as $c^{-}$ $c^{\prime-}$,
otherwise there is a containment relation between characters, i.e. either $c$
includes $c^{\prime}$ or vice versa, contradicting the fact that characters
are maximal ones.

Let us now consider the case that $c^{-}$ and $c^{\prime-}$ appear in two
distinct paths of $T_{M}$. By Lemma 14, $T$ is a branch-tree.

If they are in conflict in $G_{M}$, there must exists a species $s$ of such
graph that induces the $(0,0)$ configuration in columns for characters
$c,c^{\prime}$ and such species must occurs before $c$, $c^{\prime}$ in tree
$T$. In fact, in the tree, since they are negated along distinct paths, it
means that the only way to have a species with the $(0,0)$ configuration is
just to have such species node before the occurrence of $c$ and $c^{\prime}$.
∎

The following proposition is an immediate consequence of the definition of
branch-tree and the fact that a maximal reducible graph contains no null
character.

######  Proposition 17.

Let $G_{M}$ be a maximal reducible graph solved by a branch-tree $T_{M}$, and
let $x$ be the branch-node of $T_{M}$. Then the state of $x$ consists of all
characters of $G_{M}$.

######  Lemma 18.

Let $G_{RB}$ be a connected red-black graph and let $G_{M}$ be the subgraph of
$G_{RB}$ induced by the maximal characters of $G_{RB}$. Then ${G_{M}}$ is a
connected graph.

###### Proof.

Assume to the contrary that $G_{M}$ is not connected. Since $G_{RB}$ is
connected, there exists a character $c$ in $G_{RB}$ that is adjacent to two
species $s_{1}$ and $s_{2}$ belonging to two distinct connected components of
the graph $G_{M}$, but $c$ is not in the graph $G_{M}$, i.e., $c$ is not
maximal. Since $c$ is not maximal, it must be contained in a maximal character
$c_{M}$, hence $c_{M}$ is adjacent to both $s_{1}$ and $s_{2}$ in $G_{M}$,
contradicting the assumption that $s_{1}$ and $s_{2}$ belong to two different
connected components of $G_{M}$. Thus given a character $c^{\prime}$ of a
given component of $G_{M}$ either $c$ is disjoint from $c^{\prime}$ or share a
common species with $c^{\prime}$. But since $c$ is adjacent to a species
$s^{\prime}$ such that $s^{\prime}$ is in a component that is distinct from
the one having $c^{\prime}$, and since $c^{\prime}$ is maximal in $G_{RB}$, it
follows that $c$ and $c^{\prime}$ are not comparable. Consequently, since $c$
is disjoint or is not comparable with any other character in $G_{RB}$, it
follows that $c$ is also maximal, thus contradicting the initial assumption
that $G_{M}$ is not connected. ∎

##  4 The Hasse diagram and the algorithm

In this section we explore a characterization of the Hasse diagram associated
to maximal reducible graphs.

For our purposes we are interested only in solutions of a maximal reducible
graph $G_{M}$ that is in a special form that we call _normal form_. Such a
form requires that a tree $T$ does not have two consecutive edges
$e_{1},e_{2}$ each labeled by $c^{+}$ and $c^{-}$ respectively.

######  Lemma 19.

Let $T_{M}$ be a tree solving a maximal reducible graph $G_{M}$. Then tree
$T_{M}$ can be transformed into a tree $T^{\prime}_{M}$ that solves $G_{M}$
and is in normal form.

###### Proof.

Assume that tree $T_{M}$ has two consecutive edges $e_{1},e_{2}$ each labeled
by $c^{+}$ and $c^{-}$ respectively. We distinguish the case that $e_{2}$ ends
before or in the branch-node or $e_{2}$ ends below the branch-node. Observe
that in the last case it must be that $e_{1}$ ends in the branch-node, as by
definition of branch-tree no positive character can be below the branch-node.
Now, if the first case holds, then by construction of the tree $T_{M}$, it
must be that $e_{1}$ ends in a species $s_{1}$. Since the species $s_{1}$ is
the first species having $c^{+}$ while soon after $c^{-}$ is introduced, it is
immediate that $c$ is not a maximal character, which is a contradiction with
the fact that $T_{M}$ solves $G_{RB}$. Thus the only possible case occurs when
$e_{1}$ ends in the branch-node $x$ of the tree $T_{M}$ and $x$ is not labeled
by a species, otherwise again $c$ is not a maximal character in $G_{M}$.

Now, the species $s_{2}$ that is the end of $e_{2}$ does not have character
$c$, while all the other species $s$ below $x$ along the branches distinct
from the one containing $s_{2}$ have character $c$. Observe that we can
transform tree $T_{M}$ into a tree $T^{\prime}_{M}$ by introducing species
$s_{2}$ above the branch-node $x$. Then $c^{+}$ is introduced below species
$s_{2}$ along the edge $(s_{2},x)$. Observe that this change is possible in
tree $T_{M}$, since if there exist a subtree with root $s_{2}$, then $c$ is
not maximal in tree $T_{M}$. Thus such subtree does not exist. Then
$T^{\prime}_{M}$ is in normal form.

∎

The following lemma shows that the Hasse diagram for a maximal reducible graph
$G_{RB}|C_{M}$ contains a safe chain.

######  Lemma 20.

Let $\mathcal{P}$ be the diagram for a maximal reducible graph $G_{M}$. Let
$T_{M}$ be a tree of $G_{M}$ such that the child $x$ of the root $r$ is a
source of the diagram $\mathcal{P}$. Then the longest path $<r,\ldots,z>$ of
$T_{M}$ containing the root $r$ of $T_{M}$ and consisting only of positive
edges corresponds to a safe chain of $\mathcal{P}$, called the _initial chain_
of tree $T_{M}$.

###### Proof.

Consider a tree $T_{M}$ solving the maximal reducible graph $G_{M}$. Since
$G_{M}$ cannot have singletons, the edge of $T_{M}$ incident on the root must
be positive, hence $r\neq x$. By construction of tree $T$ solving $G_{RB}$,
each node $t_{i}$ of tree $T_{M}$ is labeled by a species, while $x$ is not a
species only if $x$ is the branch-node of $T_{M}$.

First consider the case that $x$ is not a species. Then $x$ is the branch-node
of $T_{M}$. By Proposition 17, the state of $x$ consists of all characters of
$G_{M}$. Assume that the path $<r,\ldots,x>$ consists of the single edge
$(r,x)$, i.e no species is along the initial path of tree $T_{M}$. Then we
show that tree $T$ cannot be in normal form. Since $T_{M}$ is a branch tree,
and $(r,x)$ is the only edge of the initial path of a solution of $G_{M}$,
none of the species of $G_{M}$ are comparable, hence the Hasse diagram
$\mathcal{P}$ of $G_{M}$ consists of singletons $s$. Clearly, the tree $T$
must have two consecutive edges one labeled $c^{+}$ and the other labeled
$c^{-}$ which is not possible in the normal form. Indeed, we can obtain a new
solution $T_{1}$ from $T$ by replacing the edge $(r,x)$ with the path
$<r,s,x>$ (such replacement is always possible since the set of characters of
$s$ is a subset of the characters of $x$). It is immediate to notice that
$T_{1}$ is a solution of $G_{M}$ and the trivial chain of $\mathcal{P}$
consisting of the singleton $s$ corresponds to the path $<r,x>$ which is the
initial path of $T_{1}$. Thus this case proves the Lemma.

Now consider the case that $x$ is a species.

Let $p=<r,t_{1},\ldots,t_{l}>$ be the path $<r,\ldots,x>$ of $T_{M}$, where
all $t_{i}$ are species of $G_{RB}$ and $l\geq 2$, i.e. at least two species
label the initial path of tree $T_{M}$. Notice that each edge
$(t_{i},t_{i+1})$ of $p$ is either an arc of $\mathcal{P}$ or a path of
$\mathcal{P}$: in the latter case replace in $T_{M}$ the edge
$(t_{i},t_{i+1})$ of $T$ with the corresponding path of $\mathcal{P}$. It is
immediate to notice that the resulting tree is still a solution of $G_{RB}$.

Since $p$ is the longest path including positive edges, we show that $t_{l}$
must be a sink of the diagram $\mathcal{P}$. Indeed, given a species $s$ that
is a descendant of species $t_{l}$, edges that follows $t_{l}$ in tree $T_{M}$
are mixed edges or negative edges. Since it is not possible to have two
consecutive edges with $c^{+}$, $c^{-}$, because of the normal form, it
follows that any species $s$ does not include at least a character of $t_{l}$.
Hence $s$ cannot include species $t_{l}$ which must be a sink of the diagram.

If $t_{1}$ is not a source of $\mathcal{P}$, then $(w,t_{1})$ is an edge of
$\mathcal{P}$, hence the set of characters of $w$ is a subset of the set of
characters of $t_{1}$. Since the edge $(r,t_{1})$ of $T_{M}$ is labeled by the
characters of $t_{1}$, then we can replace the edge $(r,t_{1})$ of $T_{M}$
with the path $(r,w,t_{1})$. We can iterate the process until the child of $r$
in the tree is the source of the chain.

The chain is safe since the corresponding c-reduction is the initial portion
of the c-reduction associated to the tree $T_{M}$ solving $G_{M}$. ∎

As a main consequence of Lemma 20 we are able to show that given $G_{RB}$
reducible there exists a tree $T$ solving $G_{RB}$ such that it starts with
the inactive characters of a source $s$ of a safe chain of diagram
$\mathcal{P}$ for $G_{RB}|C_{M}$.

Since such a safe source may not be unique in diagram $\mathcal{P}$, the rest
of the section provides results that will be used to show that we can choose
any safe source of the diagram $\mathcal{P}$ to find the initial characters of
a tree $T$ solving $G_{RB}$.

######  Lemma 21.

Let $G_{RB}$ be a reducible graph and $\mathcal{P}$ the diagram for the graph
$G_{RB}|C_{M}$. Then there exists a solution $T$ of $G_{RB}$ and a child $x$
of the root $r$ of $T$ such that $C(x)\cap C_{M}$ is the set of characters of
a safe source $s$ of $\mathcal{P}$. The vertex $x$ is called the _initial
state_ of the tree $T$.

###### Proof.

Given a solution $T$ of $G_{RB}$, we denote with $z$ the least common ancestor
of all species of $G_{RB}$ in $T$. Without loss of generality, we can assume
that there is a single edge from the root of $T$ to $z$. Let $T_{1}$ be a
solution of $G_{RB}$ such that node $z$ minimizes the number of characters of
$C_{M}$.

We distinguish two cases, according to whether $z$ is a species of $G_{RB}$.
Case 1: assume initially that $z$ is a species, hence $C(z)\cap C_{M}$ is a
node of the diagram $\mathcal{P}$. By our construction, $C(z)\cap C_{M}$
cannot have an incoming arc in $\mathcal{P}$, otherwise we would contradict
the minimality of $T_{1}$. Then we can split the edge $(r,z)$ of $T_{1}$ into
two edges $(r,x)$ and $(x,z)$ where the label of $(r,x)$ is $C(x)\cap C_{M}$.
Clearly, by construction there exists a species $s$ of $\mathcal{P}$ with the
set $C(x)\cap C_{M}$ of characters and $s$ is a source node of the diagram
$\mathcal{P}$. Consider the tree $T_{1}|C_{M}$ that is induced by the maximal
characters of $G_{RB}$ and such that $s$ is the child of the root of
$T_{1}|C_{M}$ and is a source of diagram $\mathcal{P}$. By applying Lemma 20,
tree $T_{1}|C_{M}$ has the initial-chain which is a safe chain of diagram
$\mathcal{P}$. Finally, since $s$ is obtained by the traversal of tree
$T_{1}$, $s$ is safe in $G_{RB}$ and being the source of a safe chain of
diagram $\mathcal{P}$ is a safe source of $G_{RB}$, as desired.

Moreover, it must be that $s$ is the source of the safe chain of diagram
$\mathcal{P}$ which is the initial chain of tree $T|C_{M}$, thus proving what
is required.

Case 2: assume now that $z$ is not a species. It is immediate to notice that
the tree $T_{1}|C_{M}$, which is a solution of $G_{RB}|C_{M}$ must be a
branch-tree, by Lemma 14. Moreover, by Proposition 17, $C_{M}\subseteq C(z)$.
Let $x$ be any species of $G_{RB}$ such that the species $s$ with set of
characters $C(x)\cap C_{M}$ is a source of the diagram $\mathcal{P}$. Just as
for the previous case, we can split the edge $(r,z)$ of $T_{1}$ into two edges
$(r,x)$ and $(x,z)$ where the label of $(r,x)$ is given by $C(x)\cap C_{M}$.
Then $C(x)\cap C_{M}$ is the set of characters of a species $s$ of tree
$T_{1}|C_{M}$ where $s$ is the source of the diagram $\mathcal{P}$ of
$T_{1}|C_{M}$. Similarly as above for case 1, $s$ is a safe source of
$G_{RB}$.

∎

The following technical Lemma is used to characterize the safe chains of the
diagram $\mathcal{P}$ of a maximal reducible graph.

######  Lemma 22.

Let $G_{M}$ be a maximal reducible graph, let $\mathcal{P}$ be the diagram for
$G_{M}$, and let $T_{M}$ be a tree solving $G_{M}$. Given a chain
$\mathcal{C}$ of the diagram $\mathcal{P}$, then one of the following
statements holds:

  1. 1.

$\mathcal{C}$ is a sequence of species that occur along a path $\pi$ of the
tree $T_{M}$, where $\pi$ has only positive edges,

  2. 2.

$\mathcal{C}$ is a sequence of species that occur along a path $\pi$ of the
tree $T_{M}$, where $\pi$ has only negative edges,

  3. 3.

$\mathcal{C}$ is a sequence of species that occur along a path $\pi_{1}$
consisting only of positive edges and along a path $\pi_{2}$ consisting only
of negative edges, where paths $\pi_{1}$ and $\pi_{2}$ are subpaths of the
same path and for any character $c^{-}$ of path $\pi_{2}$ $c^{+}$ occurs along
the path that connects $\pi_{1}$ to $\pi_{2}$.

###### Proof.

Assume that chain $\mathcal{C}$ has source $s$ and sink $t$, Let us first show
that species of a chain are along the same path $\pi$ of tree $T_{M}$ that
occurs from the root to a leaf of tree $T_{M}$, by proving its contrapositive.
Let $s,s^{\prime}$ be two species that are not in the same path of $T$. By the
structure of tree $T_{M}$ stated in Lemma 14, then the least common ancestor
$x$ of $s,s^{\prime}$ is neither $s$ nor $s^{\prime}$, and the paths from $x$
to $s$ and $s^{\prime}$ contain only negative edges. Those two facts imply $s$
and $s^{\prime}$ are not comparable, hence they cannot be in a chain. Thus a
chain corresponds to a path of tree $T$.

Assume first that tree $T_{M}$ is a line-tree: in this case we can prove that
only cases (1) or (2) can happen. Assume to the contrary that the path of
$T_{M}$ connecting $s$ and $t$ contains both positive and negative edges (or
mixed edges). Assume initially that $s$ is an ancestor of $t$, and consider
the negated character $c^{-}$ that is the first to appear in such path (and
let $(s_{1},s_{2})$ be the edge labeled by $c^{+}$). Observe that by Lemma 16
characters are negated in the same order as they are introduced, hence the
edge $c^{+}$ either labels the first edge of the path or it does not label any
edge of the path. In both cases, $s_{1}$ has the character $c$, while $s_{2}$
has not, hence contradicting the assumption that $(s_{1},s_{2})$ is an edge of
the Hasse diagram. A similar argument holds when $t$ is an ancestor of $s$ and
to show that a chain my label a path only consisting of negative edges.

Consider now the case when $T_{M}$ is a branch-tree. If the path connecting
$s$ and $t$ in $T_{M}$ is entirely contained in the initial path or it is
composed only of descendants of the branching node, then condition (1) and (2)
respectively holds. Hence we only have to consider the case when the $s-t$
path contains both ancestors and descendants of the branch node. We split this
path into $\pi_{1}$ and $\pi_{2}$ which are the two subpaths of $\pi$
containing the ancestors and the descendants of the branch node, respectively,
and from which species of chain $\mathcal{C}$ are obtained. Let $x_{1}$ be the
last species of $\pi_{1}$ and let $x_{2}$ be the first species of $\pi_{2}$:
clearly $(x_{1},x_{2})$ is an edge of $\mathcal{P}$. The same argument used
for the line-tree case also proves that $\pi_{1}$ does not contain any negated
character $c^{-}$. Moreover, the edge $(x_{1},x_{2})$ of $T_{M}$ cannot be
labeled by a negated character $c^{-}$, unless character $c^{+}$ is introduced
after species $x_{1}$ along the path that connects $x_{1}$ to $x_{2}$. Indeed,
if $c^{+}$ is on path $\pi_{1}$ no species of $\pi_{2}$ can have $c$, while
$x_{1}$ has $c$, contradicting the fact that $(x_{1},x_{2})$ is an edge of
$\mathcal{P}$.

By Lemma 16 all edges of $\pi_{2}$ must be negative, completing the proof. ∎

Now we are able to show the next Lemma that gives a characterization of the
safe chains of diagram $\mathcal{P}$ of a maximal reducible graph and thus it
allows to characterize the distinct safe sources of $G_{RB}$. In the next
Lemma we use the notion of inverted path:

a path $\pi_{u,v}$ from a node $u$ of $T$ to a node $v$ of $T$ is inverted in
tree $T_{1}$ if the sequence $<s_{1},\ldots,s_{l}>$ of species of the path
$\pi_{u,v}$ is replaced in $T_{1}$ by sequence $<s_{l},s_{l-1},\ldots,s_{1}>$.

######  Lemma 23.

Let $G_{M}$ be a maximal reducible graph and let $\mathcal{C}$ and
$\mathcal{C}_{1}$ be two safe chains with distinct sources, where
$\mathcal{C}_{1}$ is not trivial. Let $T_{M}$ be a tree solving $G_{M}$ such
that $\mathcal{C}$ is the initial chain of $T_{M}$. Then $T_{M}$ is a line-
tree and $\mathcal{C}_{1}$ is the initial chain of a line-tree $T_{1}$ such
that the path $\pi_{r,v}$ where $r$ is the root of $T_{M}$ and $v$ the leaf of
$T_{M}$ is inverted in tree $T_{1}$.

(a) Phylogeny

(b) Hasse diagram

Figure 3: The chain $\mathcal{C}_{1}$ of case 1 of Lemma 23 induced by
$<{c_{1}}^{+},{c_{2}}^{+},\cdots,{c_{k}}^{+}>$

###### Proof.

First observe that by definition of $G_{M}$ the graph has no active
characters. By Lemma 22 given chain $\mathcal{C}_{1}$, the following cases are
possible: (1) the sequence $\mathcal{C}_{1}$ labels a path of tree $T_{M}$
consisting of positive edges or (2) $\mathcal{C}_{1}$ labels a path of tree
$T_{M}$ consisting of negative edges (3) $\mathcal{C}_{1}$ labels two paths
$\pi_{1}$ and $\pi_{2}$, where $\pi_{1}$ consists of positive edges and
$\pi_{2}$ consists of negative edges of tree $T_{M}$, and both paths occur
along the same path of tree $T_{M}$ and for any character $c^{-}$ of
$\pi_{2}$, it holds that $c^{+}$ labels only edges of the path that connects
the two paths.

Case 1. (Figure 3). Assume first that sequence $\mathcal{C}_{1}$ consists of
$<s_{1},s_{2},\ldots,s_{k},s_{k+1}>$ and labels a path in tree $T_{M}$
consisting of positive edges $<c_{1},\ldots,c_{k}>$ of the tree i.e. species
$s_{i}$ is the end of a positive edge labeled $c_{i}$. W.l.o.g. we assume that
each edge is labeled by a single character (the same argument applies in the
case an edge is labeled by more than one character). Now, since
$\mathcal{C}_{1}$ is not the initial chain of tree $T_{M}$, it must be that it
occurs after chain $\mathcal{C}$ in tree $T_{M}$.

We distinguish two cases. Case 1.1. Now, let $c_{0}$ be a character of $s_{1}$
that is from a species $s_{0}$ that precedes $s_{1}$ along the initial path.
We now show that $c_{1}$ and $c_{0}$ are in conflict in graph $G_{M}$. Observe
that they are not comparable as they are maximal ones, but there exists also
two species in graph $G_{M}$, one that has both characters, which is the
species $s_{1}$ and one that does not have both characters. Since $s_{1}$ is
the source of chain $\mathcal{C}_{1}$, then $s_{1}$ must be preceded by an
edge labeled $d^{-}$. But, $d^{+}$ precedes character ${c_{0}}^{+}$ as
characters are negated in the order they are introduced (see Lemma 16) and
thus $d^{+}$ is introduced in a species $s_{2}$ distinct from $s_{0}$ and not
having characters $c_{0},c_{1}$ (by the normal form of tree $T_{M}$, $d^{+}$
and $d^{-}$ cannot label two consecutive edges). This fact proves that in
graph $G_{M}$ species $s_{2}$ does not have $c_{0},c_{1}$. Consequently,
characters $c_{0},c_{1}$ are in conflict in $G_{M}$. Then $c_{0},c_{1}$ induce
a red $\Sigma$-graph in $G_{M}$ when the source species $s_{1}$ and $c_{1}$
are realized, since the species $s_{2}$ with configurations $(0,0)$ and
species $s_{0}$ with configuration $(1,0)$ for the pair $(c_{0},c_{1})$ are
not removed from graph $G_{M}$. Hence we obtain a contradiction with the fact
that the chain $\mathcal{C}_{1}$ is safe, i.e it has a safe source.

Case 1.2. Assume that there does not exist any character $c_{0}$ of $s_{1}$
that belongs also to a species $s_{0}$ that precedes $s_{1}$ along the initial
path, that is $s_{1}$ has none of the characters labeling the path of $T_{M}$
from the root to $s_{1}$. Hence we can obtain a new solution $T_{1}$ for
$G_{M}$ by regrafting the subtree of $T_{M}$ rooted at $s_{1}$ as a new child
of the root. By Lemma 9, the graph $G_{M}$ is disconnected, which is a
contradiction.

Since both cases 1.1 and 1.2 are not possible, then case 1 is not possible.

Case 2. (Figure 4). Assume that sequence $\mathcal{C}_{1}$ consists of
$<s_{k+1},\ldots,s_{1}>$ and is induced by a path in tree $T_{M}$ of negative
edges $<{c_{1}}^{-},\ldots,{c_{k}}^{-}>$ of the tree $T_{M}$, (i.e., each edge
$s_{i},s_{i+1}$ being labeled by $c_{i}^{-}$) — by maximality of all
characters of $G_{M}$, no two negated characters can label the same edge. By
Lemma 16 the sequence of characters $<{c_{1}}^{+},\ldots,{c_{k}}^{+}>$ appears
in the initial path above the edge $c_{1}^{-}$ — notice that those positive
characters might be interleaved with other characters.

First we will prove that no such interleaving can happen, that is no positive
character occurs between two consecutive characters ${c_{i}}^{+}$,
${c_{i+1}}^{+}$ for $i\in\\{1,\ldots,k-1\\}$.

Assume to the contrary that a character $d^{+}$ occurs between $c_{i}^{+}$ and
$c_{i+1}^{+}$ in $T_{M}$.

Then $d^{+}$ is in conflict with character $c_{k}^{+}$ in $G_{M}$. Indeed,
$d^{+}$ and ${c_{k}}^{+}$ are not comparable (being maximal characters) and
there exists a species of $G_{M}$ that contains $d,c_{k}$, which is species
$s_{k}$ of chain $\mathcal{C}_{1}$. Indeed, it must be that $d^{-}$ cannot
label an edge of chain $\mathcal{C}_{1}$ (otherwise $\mathcal{C}_{1}$ is not
the correct chain), and thus $d^{-}$ must occur on a path distinct from the
one of $\mathcal{C}_{1}$, in virtue of Lemma 16. Moreover, there is also a
species $w_{1}$ not having $c_{k}$ and $d$, which is the one occurring before
${c_{i}}^{+}$. Observe that there is at least a species having $d$ and not
$c_{k}$ which is the species $w_{2}$ that is the end of edge labeled $d^{+}$
along the path $<{c_{1}}^{+},\ldots,{c_{k}}^{+}>$. Since $w_{1}$ and $w_{2}$
are not realized before the species $s_{k}$ of chain $\mathcal{C}_{1}$, the
conflict between $d,c_{k}$ cannot be removed when the chain $\mathcal{C}_{1}$
is realized, that is $d,c_{k}$ induce a red $\Sigma$-graph after the
realization of the species $s_{k+1}$ of chain $\mathcal{C}_{1}$. It follows
that chain $\mathcal{C}_{1}$ cannot be safe in $G_{M}$, a contradiction with
the initial assumption. Thus it must be that no positive character occurs
between two consecutive characters ${c_{i}}^{+},{c_{i+1}}^{+}$ in tree
$T_{M}$. Observe that the above argument showing that $d^{-}$ cannot occur on
a path distinct from the one having chain $\mathcal{C}_{1}$ shows that the
path labeled by $<{c_{1}}^{-},\ldots,{c_{k}}^{-}>$ does not have branches for
characters introduced after $<{c_{1}}^{+},\ldots,{c_{k}}^{+}>$. Moreover, it
cannot have branches due to the negation of characters that precede character
$<{c_{1}}^{-}$, since otherwise there exist a character $c$ that is negated
after one that is introduced in the initial path after $c$, contradicting
Lemma 16. It follows that the path labeled $<{c_{1}}^{-},\ldots,{c_{k}}^{-}>$
is simple.

To complete the proof of case 2, we show the following. Claim (1): the
sequence of edges $<{c_{1}}^{-},\ldots,{c_{k}}^{-}>$ is not followed in tree
$T_{M}$ by any other characters (positive or negative). This fact shows that
the tree $T_{M}$ is a line-tree since the edge labeled ${c_{1}}^{-}$ is
preceded by an edge labeled by a positive character and thus no branch-node
occurs before sequence $<{c_{1}}^{-},\ldots,{c_{k}}^{-}>$ and no branch-node
occurs after being this path simple. In virtue of Lemma 15 it follows that we
can build a tree $T^{\prime}_{M}$ by reading the tree $T_{M}$ in inverted
order that is from the leaf to the root. Thus this case proves that
$\mathcal{C}_{1}$ is the initial chain of the tree $T^{\prime}_{M}$ and this
concludes the proof of the Lemma.

In order to prove Claim (1) we prove the following Claim (2): the path labeled
$<{c_{1}}^{+},\ldots,{c_{k}}^{+}>$ is followed by a positive character $d^{+}$
before the occurrence of $<{c_{1}}^{-},\ldots,{c_{k}}^{-}>$ if $d^{+}$ cannot
be negated in the tree, that is the path labeled
$<{c_{1}}^{-},\ldots,{c_{k}}^{-}>$ ends in a leaf of the tree. Observe that if
$<{c_{1}}^{+},\ldots,{c_{k}}^{+}>$ is followed only by negative characters,
then the sequence $<{c_{1}}^{-},\ldots,{c_{k}}^{-}>$ does not induce a chain,
since the chain ends in a different sink node. Now, assume that a character
$d^{+}$ follows sequence $<{c_{1}},\ldots,{c_{k}}>$.

Let us recall that by Lemma 16, positive characters are introduced in the same
order they are negated if they occur negated along the same path.
Consequently, it must be that $d^{+}$ is negated along a path distinct from
the one having chain $\mathcal{C}_{1}$ (i.e. $T_{M}$ is a branch-tree). Assume
that $d$ is negated below the negation of character $c_{i}$ of chain
$\mathcal{C}_{1}$, where $1\leq i<k$, (otherwise if $i=k$ or then
$\mathcal{C}_{1}$ has a different source node) and thus there exists a species
$w_{1}$ having $c_{k}$ but not $d$, where $w_{1}$ is the end of the branch
having $d^{-}$. Observe that in chain $\mathcal{C}_{1}$ the species $s_{k}$
contains characters $c_{k}$ and $d$. These two characters share a common
species, are not comparable and there exists clearly a species $w_{2}$ without
both characters $c_{k}$ and $d$, which is a species of chain
$<{c_{1}}^{+},\ldots,{c_{k}}^{+}>$. Thus they are in conflict in $G_{M}$. Now,
after the realization of $s_{k}$ it holds that $c_{k}$ and $d$ induces a red
$\Sigma$-graph in $G_{M}$ as the species $w_{2}$ with configuration $(0,0)$
for the pair $(c_{k},d)$ is not realized before $s_{k}$ and similarly there
are species with configuration $(1,0)$ and $(0,1)$ that are not realized
before $s_{k}$ such as the species in which edge labeled ${c_{k}}^{+}>$ ends.
Thus we obtain a contradiction with the fact the chain $\mathcal{C}_{1}$ is
safe.

As a consequence of Claim (2), either there is no character that follows path
labeled $<{c_{1}}^{-},\ldots,{c_{k}}^{-}>$ proving Claim (1), otherwise there
exists no character $d^{+}$ that follows the path labeled
$<{c_{1}}^{+},\ldots,{c_{k}}^{+}>$. Thus if there exists a character $c$ that
is after sequence $<{c_{1}}^{-},\ldots,{c_{k}}^{-}>$, $c$ is disjoint from the
other characters in $G_{M}$, which contradicts the fact that $G_{M}$ is
connected. Moreover, no negative character occurs after sequences
$<{c_{1}},\ldots,{c_{k}}>$ $<{c_{1}}^{-},\ldots,{c_{k}}^{-}>$ because of the
ordering of characters. Thus Claim (1) holds.

Case 3. (Figure 5). Assume that the sequence $\mathcal{C}_{1}$ consists of
sequence $<w_{1},w_{2},\ldots,w_{l}>$ (induced in tree $T_{M}$ by a path
labeled by consecutive positive characters $<b_{1},b_{2},\ldots,b_{l}>$ )
followed by sequence $<s_{k+1},\cdots,s_{1}>$ that is induced in tree $T_{M}$
by a path labeled by consecutive negative characters
$<{c_{1}}^{-},\cdots,{c_{k}}^{-}>$ of the tree. More precisely, each edge
$(s_{i},s_{i+1})$ is labeled $c_{i}^{-}$ — by maximality of all characters of
$G_{M}$, no two negated characters can label the same edge, $w_{i}$ is the end
of the edge labeled $b_{i}$ when $1\leq i\leq l$. Then we show the following
Claim (3): there exists no character in tree $T_{M}$ that precedes sequence
$<b_{1},b_{2},\cdots,b_{l}>$. This fact shows that chain $\mathcal{C}_{1}$
share the same source node of chain $\mathcal{C}$ thus contradicting the
assumption that they have distinct sources. Observe that case 3 implies that
for each character ${c_{i}}^{-}$, then ${c_{i}}^{+}$ occurs after
$<b_{1},b_{2},\ldots,b_{l}>$. Now, by Lemma 22, it must be that the sequence
of positive edges $<{{c^{+}}_{1}},\ldots,{{c^{+}}_{k}}>$ occurs before
sequence $<{c_{1}}^{-},\ldots,{c_{k}}^{-}>$ and after sequence
$<b_{1},b_{2},\ldots,b_{l}>$. This fact implies that
path$<{c_{1}}^{-},\ldots,{c_{k}}^{-}>$ occurs below the branch-node as the
negated characters $<{b_{1}}^{-},{b_{2}}^{-},\ldots,{b_{l}}^{-}>$ must occur
below the branch-node of tree $T_{M}$. Similarly, a positive character $d^{+}$
that occurs before $<{b_{1}}^{-},{b_{2}}^{-},\ldots,{b_{l}}^{-}>$ must occur
negated below the branch node. Let us prove Claim (3). Assume to the contrary
that a character $d^{+}$ occurs before ${b_{1}}^{+}$. Since chain
$\mathcal{C}_{1}$ does not contain $d^{-}$ it must be that $d^{-}$ occurs
along a distinct path of the one having $\mathcal{C}_{1}$ and from the one
having $<{b_{1}}^{-},{b_{2}}^{-},\ldots,{b_{l}}^{-}>$. But, then the species
$w_{2}$ of $\mathcal{C}_{1}$ has character $d^{+}$. Observe that since chain
$\mathcal{C}_{1}$ starts with the positive edge $<{b_{1}}^{+}$ it must be that
there exists a species before $w_{1}$ with a positive character distinct from
$d^{+}$ that is then negated after $d^{+}$. In other words there exists a
species $s_{0}$ without the pair $d^{+}$ and ${b_{1}}^{+}$. The two characters
are not comparable (they are maximal ones) and they are in the same species
$w_{2}$, thus they are conflicting in $G_{M}$. But, when $w_{2}$ is realized
they induce a red $\Sigma$-graph as the species with configuration $(0,0)$ and
$(1,0)$ are not all removed from $G_{M}$ when realizing $w_{2}$. Thus this
would contradict that $\mathcal{C}_{1}$ is safe, thus proving that Claim 3
holds. ∎

A main consequence of the proof of the previous Lemma 23 is the fact that if
the diagram of a maximal reducible graph is non degenerate then there are at
most two trees solving the same maximal reducible graph such that the initial
chain of such trees starts with distinct sources.

######  Lemma 24.

Let $G_{RB}$ be a reducible graph. Let $G_{RB}|C_{M}$ be a maximal reducible
graph whose diagram $\mathcal{P}$ is not degenerate. Then diagram
$\mathcal{P}$ has at most two distinct safe chains and at most two safe
sources for $G_{RB}$.

(a) Phylogeny

(b) Hasse diagram

(c) Alternative Phylogeny

Figure 4: The chain $\mathcal{C}_{1}$ of case 2 of Lemma 23 induced by
$<{c_{1}}^{-},{c_{2}}^{-},\cdots,{c_{k}}^{-}>$

(a) Phylogeny

(b) Hasse diagram

(c) Alternative Phylogeny

Figure 5: The chain $\mathcal{C}_{1}$ of case 3 of Lemma 23 induced by
$<{b_{1}},{b_{2}},\ldots,{b_{l}}>$ and
$<{c_{1}}^{-},{c_{2}}^{-},\ldots,{c_{k}}^{-}>$

###  4.1 The degenerate diagram

If the diagram $\mathcal{P}$ for graph $G_{RB}|C_{M}$ is degenerate, then the
notion of safe source for $G_{RB}$ is defined differently as follows.

######  Definition 25 (safe source in a degenerate diagram).

Let $G_{RB}$ be a reducible graph such that $G_{RB}|C_{M}$ has a degenerate
diagram. Then a source $s$ of $\mathcal{P}$ is safe for $G_{RB}$ if $C(s)$ are
realized in graph $G_{RB}$ without inducing red $\Sigma$-graphs and either (1)
$s$ is a species of $G_{RB}$ or (2) $s$ is not a species of $G_{RB}$ and none
of the sources of $\mathcal{P}$ is a species of $G_{RB}$.

A _degenerate tree_ $T_{M}$ for a maximal reduced graph that is not in normal
form is a branch-tree whose branches are single edges outgoing from the
branch-node each labeled by a single negative character of the graph; only the
leaves are labeled by species. Then a degenerate tree in normal form is
obtained by moving one of the leaves in the initial path and then removing the
edge labeled by the negated character that ends in the leaf. Observe that
given a degenerate tree $T_{M}$ solving $G_{M}$ that is in normal form with
$s$ the species of the initial path, then for each each leaf $s_{i}$ of tree
$T_{M}$ there exists a tree ${T^{i}}_{M}$ solving $G_{M}$ such that is
obtained by inverting the species $s_{i}$ with the species $s$ (see Figure 9).

######  Lemma 26.

Let $G_{M}$ be a maximal reducible graph such that its diagram is degenerate
and let $T_{M}$ be a tree solving $G_{M}$. Then the tree $T_{M}$ is a
degenerate tree and the graph $G_{M}$ has no conflicting characters.

###### Proof.

Assume first that the initial-path of the tree $T$ has more than one species.
Then the species are ends of mixed edges since they cannot be included one in
the other. In the following we show that there cannot be two consecutive mixed
edges in the tree $T$. Assume to the contrary that we have two consecutive
mixed edges that negate the characters $c,c^{\prime}$ one after the other. It
is not restrictive to assume that these two edges are the first ones to occur
along the initial-path of tree $T$. Observe that the two characters must be
introduced together otherwise there are species one included in the other. But
as a consequence of this fact, character $c^{\prime}$ includes character $c$,
which is a contradiction. As a consequence of this fact there is at most one
species $s$ along the initial path of tree $T$. Then we show that each branch
of the tree consists of a single edge labeled only by a negated character.
Indeed, otherwise a branch may have at least two species $s,s^{\prime}$ one
included in the other as they differ only by the negation of characters, which
contradicts the fact that the diagram has only singletons. Let us now show
that each branch is labeled by a single character. Otherwise, it is easy to
show that the characters labeling a branch edge are identical characters in
the graph, which contradicts the initial assumption, or they are not maximal
ones. As a consequence of the above observations it follows that all the
characters that are negated along the branches occur on the edge ending in
species $s$ or they occur on the initial path which has no species. It follows
that the tree is a degenerate one as required. It is immediate to show that
the graph has no conflicting characters ∎

######  Theorem 27.

Let $G_{RB}$ be a reducible graph. Let $G_{RB}|C_{M}$ be a maximal reducible
graph whose diagram $\mathcal{P}$ is degenerate and let $s$ be a safe source
of $G_{RB}$. Then there exists a solution $T$ of $G_{RB}$ such that the child
$x$ of the root $r$ of $T$ is labeled by the characters of $s$ that are
inactive in $G_{RB}$.

###### Proof.

By definition of safe source for $G_{RB}$ we have to distinguish two cases.
Let $T$ be a tree solving $G_{RB}$ and let $T_{M}=T|C_{M}$ be the tree solving
$G_{RB}|C_{M}$. Case 1: assume first that $s$ is not a species of $G_{RB}$,
i.e., by definition any safe source of the diagram is safe for $G_{RB}$. Then
given $T_{M}$ we need to consider two cases. Case 1.1 Assume that tree $T_{M}$
is not in normal form. This fact implies that if there exists a species
$s_{1}$ below the root of tree $T$ which is on the path of tree $T$ including
the initial path of tree $T_{M}$, then $s_{1}$ includes all the characters of
$C_{M}$. Then we can split the edge $(r,s_{1})$ into two edges $(r,s)$ and
$(s,s_{1})$, where the first is labeled by the characters of $s$ that are
inactive in $G_{RB}$, thus proving the Theorem. Otherwise it means that no
species is along the path that includes the initial path of tree $T_{M}$, but
then we can find a state $s$ of tree $T$ corresponding to the safe species $s$
of $\mathcal{P}$.

Case 1.2 Assume that tree $T_{M}$ is in normal form, i.e., there exists a
species $v$ along the initial path of tree $T_{M}$. Since by assumption $s$ is
not a species of $G_{RB}$, there exists a species $s_{1}$ of graph $G_{RB}$
including $s$ such that $s_{1}$ also includes at least a non maximal character
$x$. Let $s_{1}$ be the species with the minimum number of characters
including $s$. Observe that such a species exists in tree $T$. Now, if tree
$T$ starts with species $s_{1}$ it is immediate that the Theorem holds, since
$T$ is the tree satisfying the Theorem. Thus we must consider the case that
$s_{1}$ is a species of tree $T$ but $s_{1}$ is along a path of tree $T$ that
is not the one including the initial path of tree $T_{M}$, that is $s$ is a
leaf of tree $T_{M}$. Moreover, observe that $s_{1}$ must be a leaf of tree
$T$ because of the structure of degenerate trees. Let us recall that by the
structure of the degenerate tree it must be that $s$ consists of set
$C_{M}\setminus\\{c_{0}\\}$. Now, by Theorem 26 we know that there exists
another tree ${T^{1}}_{M}$ with species $s$ in the initial path and solving
$G_{RB}|C_{M}$ such that tree ${T^{1}}_{M}$ is obtained by inverting the path
$\pi_{v,s}$ labeled $<v,s>$ of tree ${T}_{M}$. Now, it is easy to show that
the tree ${T^{1}}_{M}$ can be extended to a solution $T_{1}$ for graph
$G_{RB}$. Indeed, we build tree $T_{1}$ from $T$ by inverting the species of
the path of tree $T$ that includes path $\pi_{v,s}$. We then show that tree
$T_{1}$ represents all the species of graph $G_{RB}$ and hence is a solution
of $G_{RB}$ and moreover $T_{1}$ is such that starts with species $s_{1}$,
consequently it is the tree that satisfies the Theorem. First observe that the
inverting the path is possible if there are no active characters in $G_{RB}$
otherwise, it is immediate to show that $s$ cannot be a safe source of
$\mathcal{P}$, as it cannot have active characters in $G_{RB}$ which is not
possible. Indeed, observe that the path $\pi_{1}$ of tree $T_{1}$ that
includes the initial path of tree ${T^{1}}_{M}$ includes the same set of
maximal and non maximal characters of the path $\pi$ of tree $T$ that includes
the initial path of tree $T_{M}$. Now, the species that are below the path
$\pi_{1}$ in tree $T$ can be also represented in tree $T_{1}$ along the
branches that are identical in the two trees $T_{1}$ and $T$ since such
species derive by the negation of characters in $\pi$ or adding new
characters. In particular notice that the characters that are negated along
one branch of tree $T_{1}$ are the same to be negated along the same branch of
tree $T$. It follows that all species of the paths different from the inverted
one are also represented in $T_{1}$. Case 2: assume that $s$ is a species of
$G_{RB}$. Then given tree $T$ we must consider two cases. Case 2.1 Assume that
$s$ occurs as the first species of tree $T$. Then the Lemma holds.

Case 2.2 Assume that $s$ does not occur as the first species of tree $T$. Now,
let $T_{M}=T|C_{M}$ be the tree induced by the maximal characters and let
${T^{1}}_{M}$ be the tree that is obtained from $T_{M}$ by inverting the path
$\pi$ from the root $r$ to node $v$ such that $\pi$ ends in species $s$, that
is $v=s$ (observe that such path exists). In the following we show that the
tree $T_{1}$ obtained from tree $T$ inverting the path that includes $\pi$ is
a tree solving $G_{RB}$. First observe that inverting the path is possible if
there are no active characters in $G_{RB}$ otherwise, it is immediate to show
that $s$ cannot be a safe source of $\mathcal{P}$, as it cannot have active
characters in $G_{RB}$ which is not possible. Now, we need to show that $s$ is
a species of tree $T_{1}$ and is the first species of tree $T_{1}$. But since
$s$ is a species of tree $T$ and being $s$ the leaf of tree ${T}_{M}$ it
follows that $s$ must be a leaf of tree $T$. It is immediate that tree $T_{1}$
is the tree that satisfies the Lemma thus proving what is required. In fact it
is enough to observe that tree $T_{1}$ contains all the species of tree $T$
and thus by construction it solves $G_{RB}$ as $T$ solves $G_{RB}$. ∎

###  4.2 Step 1 of the algorithm

As a consequence of the Lemma 21 we are able to show that there exists a tree
$T$ for $G_{RB}$ such that the inactive characters of the first state below
the root consists of the characters of a safe source of the diagram
$\mathcal{P}$ for $G_{RB}|C_{M}$.

This result is a main consequence of the fact that a tree $T$ starts with the
characters of a tree solving the maximal reducible $G_{RB}|C_{M}$ and such set
of characters correspond to those of a safe chain $\mathcal{C}$ of diagram
$\mathcal{P}$ (see lemma 20) and clearly since these characters are obtained
by a tree traversal of tree $T$ their realization does not induce red
$\Sigma$-graphs in $G_{RB}$, i.e., the source of the chain $\mathcal{C}$ is
safe in $G_{RB}$.

A stronger result states in Theorem 28 can be proved: for any safe source $s$
of $G_{RB}$, there exists a tree $T$ solving $G_{RB}$ such that the set of
characters of $s$ gives the inactive characters of the first state below the
root $r$ of tree $T$. Thus we show that we are able to compute in polynomial
time the first state of a tree $T$ solving a graph $G_{RB}$.

Observe that the result is a consequence of the previous characterization of
trees solving a maximal reducible graph: there are at most two safe chains of
diagram $\mathcal{P}$ that have distinct sources and are the initial chains of
two trees solving $G_{M}$ and such trees are two line-trees $T_{1}$ and
$T_{2}$, one tree being the inverted path of the other tree.

######  Theorem 28.

Let $G_{RB}$ be a reducible graph, let $\mathcal{P}$ be the diagram for a
maximal reducible graph $G_{RB}|C_{M}$ that is not degenerate, and let $s$ be
a safe source of $G_{RB}$. Then there exists a solution $T$ of $G_{RB}$ such
that the child $x$ of the root $r$ of $T$ is labeled by the characters of $s$
that are inactive in $G_{RB}$. The vertex $x$ is called the _initial state_ of
the tree $T$.

###### Proof.

By Lemma 21 there exists a tree $T$ solving $G_{RB}$ such that its root has a
child node $x$ such that $x$ is a safe source of diagram $\mathcal{P}$. Let
$T_{M}$ be the tree $T|C_{M}$ induced by the maximal characters of $T$.

Since $\mathcal{P}$ is not degenerate, by Lemma 23 there are at most two trees
that solve the graph $G_{M}$ and have distinct sources. If the diagram has a
unique safe source the Lemma follows since $s$ is the unique safe source. Thus
assume that there is another tree $T^{\prime}_{M}$ that solves the graph
$G_{M}$: by Lemma 23 such tree is obtained from tree $T_{M}$ which is a line-
tree by reading it in inverted order. Assume now that the graph $G_{RB}$ has
no active characters. Since tree $T$ is obtained by inserting characters in
tree $T_{M}$ and adding subtrees to states of tree $T_{M}$, it is immediate to
show that a tree $T^{\prime}$ solving $G_{RB}$ can be also obtained from tree
$T^{\prime}_{M}$ by reading the tree $T$ in inverted order from the leaf $v$
of tree $T_{M}$. This fact proves the Lemma in this case. Assume now that the
graph $G_{RB}$ has active characters. Now, the other tree ${T^{\prime}}_{M}$
solving $G_{RB}|C_{M}$ starts with a source that is the leaf $v$ of tree
$T_{M}$. Observe that the smallest species of tree $T$ solving $G_{RB}$ and
including $v$ does not have the active characters of $G_{RB}$. Indeed, by
Lemma 16 characters that occur negated along the same path must be introduced
as positive ones in the same order they are negated. Thus state $v$ cannot be
the initial state of another tree $T_{1}$ solving $G_{RB}$. ∎

###  4.3 Step 2 of the algorithm

We can now state the main Lemma used in the recursive step of our algorithm 1
Reduce.

######  Theorem 29.

Let $G_{RB}$ be a reducible graph and let $\mathcal{P}$ be the diagram for
$G_{RB}|C_{M}$. Let $s$ be a safe source of diagram $\mathcal{P}$. Then the
graph $G_{RB}^{\prime}$ obtained after the realization of $s$ is reducible.

###### Proof.

By Theorem 28, the source $s$ is the initial state of a tree $T$ solving graph
$G_{RB}$. Thus the realization of the sequence of characters of $s$ is the
initial sequence of a successful reduction for graph $G_{RB}$. Indeed, the
tree traversal of tree $T$ produces a successful reduction in virtue of
Proposition 6. Consequently the realization of $s$ on graph $G_{RB}$ produces
a reducible graph.

∎

The following result is a natural consequence of the fact that the number of
chains in a degenerate diagram for graph $G_{RB}$ is at most the number of
characters of $G_{RB}$.

######  Lemma 30.

The total number of distinct chains in a diagram $\mathcal{P}$ for a maximal
reducible graph $G_{RB}$ is polynomial in the number of characters of the
diagram.

###### Proof.

Let $T$ be a tree solving $G_{RB}$. Given a chain $\mathcal{C}$, then an
internal node $x$ of the chain has outdegree greater than $1$ when $x$ is
adjacent to a species obtained by the negation of some characters of the chain
below the node $x$. Now, the negation of such characters occur only once in
the tree $T$ producing a number of distinct chains that is linear in the
number of characters. This observation is enough to prove the Lemma.

∎

######  Lemma 31.

Let $G_{RB}$ be a maximal reducible graph and let $\mathcal{P}$ be the diagram
for $G_{RB}$. Then the number of safe chains in $G_{RB}$ is polynomial in the
number of characters and a safe chain is computed in polynomial time.

###### Proof.

By Lemma 30 the number of distinct chains in diagrams $\mathcal{P}$ that we
need to test to be safe is polynomial in the number if characters. A chain
$\mathcal{C}$ is safe for a red-black graph if the realization of the sequence
of characters labeling the edges of the chain does not induce a red
$\Sigma$-graph. It is easy to verify that such test can be done in polynomial
time. ∎

The following is a direct consequence of Lemma 31.

######  Lemma 32.

Let $G_{RB}$ be a reducible graph. The total number of distinct safe sources
is polynomial in the number of characters of the diagram and a safe source is
computed in polynomial time.

Algorithm 1 describes the procedure Reduce$(G_{RB})$ that given a red-black
graph (with active and non active characters) computes an extended c-reduction
that is a successful reduction of $G_{RB}$ if $G_{RB}$ can be solved by a tree
$T$.

Input : A red-black graph $G_{RB}$

Output : A c-reduction of the graph $G_{RB}$, if it exists. Otherwise, it
aborts.

1 Remove all singletons from $G_{RB}$ ;

2 if  _$G_{RB}$ is empty_ then

3 return the empty sequence;

4

5if  _$G_{RB}$ has a free character $c$_ then

6 $G_{RB}\leftarrow$ Realize$(G_{RB},c^{-})$;

7 return $(<c^{-},Reduce(G_{RB})>)$;

8

9if  _$G_{RB}$ has a universal character $c$_ then

10 $G_{RB}\leftarrow$ Realize$(G_{RB},c^{+})$;

11 return $(<c^{+},Reduce(G_{RB})>)$;

12

13if  _$G_{RB}$ is disconnected_ then

14 return the concatenation of $Reduce(G_{RB}^{i})$ for each connected
component $G_{RB}^{i}$ of $G_{RB}$ ;

15

16$C_{M}\leftarrow$ the maximal characters of $G_{RB}$ ;

17 ${\cal P}\leftarrow$ the diagram for $G_{RB}|C_{M}$;

18 if  _no safe source of the diagram ${\mathcal{P}}$ exists_ then

19 Abort;

20

21$s\leftarrow$ a safe source of the diagram $\mathcal{P}$;

22 $S_{c}\leftarrow$ the sequence of positive characters of $s$ that are
inactive in $G_{RB}$ ;

23 $G_{RB}\leftarrow$ Realize$(G_{RB},S_{c})$;

24 return $<S_{c},Reduce(G_{RB})>$;

Algorithm 1 Recursive Reduce. Realize is a function that returns the new red-
black graph after the realization of a sequence of characters

Notice that Algorithm 1, when applied to a graph $G_{RB}$, computes a
successful reduction $R$ of $G_{RB}$ (if it exists). A successful reduction
can then be transformed into a persistent phylogeny for $G_{RB}$— see
Algorithm Reduction2Phylogeny [7]).

######  Theorem 33.

Let $G_{RB}$ be a reducible red-black graph. Then Algorithm 1 computes a tree
$T$ solving $G_{RB}$ in polynomial time.

###### Proof.

The correctness of Algorithm 1 can be proved by induction on the length $n$ of
the reduction found.

If $n=0$, then the red-black graph $G_{RB}$ must be edgeless, hence line 1
removes all vertices of $G_{RB}$ and the condition at line 1 holds. The empty
reduction that is computed is trivially correct.

If $n=1$, then the reduction solving $G_{RB}$ is either $c^{+}$ or $c^{-}$. In
the both cases, the character $c$ is the only character of $G_{RB}$ that is
not a singleton. It is immediate to notice that in the first case $c$ is a
universal character and in the second case $c$ is a free character, and the
reduction that is computed is correct.

Let us now consider the case $n\geq 2$. If $G_{RB}$ is disconnected, by
Observation 8, the reduction solving $G_{RB}$ is the concatenation of the
reduction solving each connected component of $G_{RB}$. The correctness of
lines 1, 1 is immediate.

Consider now the case when $G_{RB}$ is connected. If $G_{RB}$ has a universal
or a free character, then the algorithm computes the correct reduction by
inductive hypothesis. If $G_{RB}$ has no universal or free characters, then
lines 1–1 are reached. By Theorem 9 and Theorem 28, if the diagram
$\mathcal{P}$ is degenerate, there exists a solution $T$ of $G_{RB}$ such that
the topmost edge is labeled by the set $X$ of the characters of $C_{M}$ (which
are all inactive in $G_{RB}$) that are possessed by a safe source $s$ of
$G_{RB}$. Notice that the reduction associated with $T$ begins with the
characters $X$, hence lines 1–1 of the algorithm correctly compute the
reduction.

A direct consequence of Lemmas 24 is that either $G_{RB}$ has only a safe
source, or $G_{RB}$ has two safe sources $s_{1}$ and $s_{2}$, if the diagram
$\mathcal{P}$ is not degenerate. Otherwise, if the diagram is degenerate by
definition of safe source given in Definition 25 it is immediate to compute
the correct safe source for which Theorem 27 holds. In the latter case, there
exist two solutions $T_{1}$ and $T_{2}$ of $G_{RB}$ such that $s_{1}$ is the
topmost species of $T_{1}$ and $s_{2}$ is the topmost species of $T_{2}$,
hence choosing any of $s_{1}$ or $s_{2}$ is correct.

Since each invocation of Algorithm 1 computes at least a signed character of
the reduction and the reduction contains at most $2m$ signed characters, the
overall time complexity is polynomial, if computing a safe source has
polynomial time complexity, which is a consequence of Lemma 31. ∎

Notice that the same argument shows that applying Algorithm 1 to a red-black
graph $G_{RB}$ that has no solution, then Algorithm 1 requires polynomial time
and either aborts or computes an incorrect tree — checking if a tree is
actually a solution of $G_{RB}$ is immediate.

##  5 Conclusions

The Persistent Phylogeny model has appeared many times in the literature under
different formulations [16], but its computational complexity has been open
for 20 years. In this paper we have answered this question by providing a
polynomial-time algorithm that determines if a binary matrix has a persistent
phylogeny and constructs such a persistent phylogeny if it exists.

A natural optimization criterion is to compute a tree with the smallest number
of persistent characters — this is equivalent to computing the tree with the
fewest edges. The computational complexity of this optimization problem is an
open problem. We believe that the graph theoretic approach developed in the
paper could shed some light into the solution of this problem.

## References

  * [1] R. Agarwala and D. Fernández-Baca.  A Polynomial-Time Algorithm For the Perfect Phylogeny Problem When the Number of Character States is Fixed.  SIAM Journal on Computing, 23(6):1216–1224, Dec. 1994.
  * [2] V. Bafna, D. Gusfield, G. Lancia, and S. Yooseph.  Haplotyping as perfect phylogeny: A direct approach.  Journal of Computational Biology, 10(3-4):323– 340, 2003.
  * [3] C. Benham, S. Kannan, M. Paterson, and T. Warnow.  Hen’s teeth and whale’s feet: generalized characters and their compatibility.  Journal of Computational Biology, 2(4):515–525, 1995.
  * [4] H. L. Bodlaender, M. R. Fellows, and T. J. Warnow.  Two strikes against perfect phylogeny.  In Automata, languages and programming (Vienna, 1992), volume 623 of Lecture Notes in Comput. Sci., pages 273–283. Springer, Berlin, 1992\.
  * [5] P. Bonizzoni, C. Braghin, R. Dondi, and G. Trucco.  The binary perfect phylogeny with persistent characters.  Theoretical computer science, 454:51–63, 2012.
  * [6] P. Bonizzoni, A. P. Carrieri, G. Della Vedova, R. Dondi, and T. M. Przytycka.  When and How the Perfect Phylogeny Model Explains Evolution.  In N. Jonoska and M. Saito, editors, Discrete and Topological Models in Molecular Biology, Natural Computing Series, pages 67–83. Springer Berlin Heidelberg, Berlin, Germany, 2014.
  * [7] P. Bonizzoni, A. P. Carrieri, G. Della Vedova, R. Rizzi, and G. Trucco.  A colored graph approach to perfect phylogeny with persistent characters.  Theoretical Computer Science, pages –, 2016.
  * [8] P. Bonizzoni, A. P. Carrieri, G. Della Vedova, and G. Trucco.  Explaining evolution via constrained persistent perfect phylogeny.  BMC Genomics, 15(Suppl 6):S10, Oct. 2014.
  * [9] A. Brandstadt, V. B. Le, and J. Spinrad.  Graph Classes. A Survey.  SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, PA, 1999.
  * [10] J. H. Camin and R. R. Sokal.  A method for deducing branching sequences in phylogeny.  Evolution, 19(3):pp. 311–326, 1965.
  * [11] R. Diestel.  Graph Theory, volume 173 of Graduate Texts in Mathematics.  Springer-Verlag, Heidelberg, third edition, 2005.
  * [12] Z. Ding, V. Filkov, and D. Gusfield.  A linear time algorithm for Perfect Phylogeny Haplotyping (pph) problem.  Journal of Computational Biology, 13(2):522–553, 2006.
  * [13] M. El-Kebir, L. Oesper, H. Acheson-Field, and B. J. Raphael.  Reconstruction of clonal trees and tumor composition from multi-sample sequencing data.  Bioinformatics, 31(12):i62–i70, June 2015.
  * [14] M. El-Kebir, G. Satas, L. Oesper, and B. Raphael.  Inferring the mutational history of a tumor using multi-state perfect phylogeny mixtures.  Cell Systems, 3(1):43 – 53, 2016.
  * [15] D. Fernández-Baca and J. Lagergren.  A polynomial-time algorithm for near-perfect phylogeny.  SIAM J. Comput., 32(5):1115–1127, 2003.
  * [16] L. A. Goldberg, P. W. Goldberg, C. A. Phillips, E. Sweedyk, and T. Warnow.  Minimizing phylogenetic number to find good evolutionary trees.  Discrete Applied Mathematics, 71(1–3):111–136, Dec. 1996.
  * [17] D. Gusfield.  Efficient algorithms for inferring evolutionary trees.  Networks, pages 19–28, 1991.
  * [18] D. Gusfield.  Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology.  Cambridge University Press, Cambridge, 1997.
  * [19] D. Gusfield.  Persistent phylogeny: a galled-tree and integer linear programming approach.  In Proceedings of the 6th ACM Conference on Bioinformatics, Computational Biology and Health Informatics, pages 443–451. ACM, 2015.
  * [20] S. Kannan and T. Warnow.  A fast algorithm for the computation and enumeration of perfect phylogenies.  SIAM Journal on Computing, 26(6):1749–1763, 1997.
  * [21] J. Maňuch, M. Patterson, and A. Gupta.  On the generalised character compatibility problem for non-branching character trees.  In Computing and Combinatorics, pages 268–276, 2009.
  * [22] J. Manuch, M. Patterson, and A. Gupta.  Towards a characterisation of the generalised cladistic character compatibility problem for non-branching character trees.  In ISBRA, pages 440–451, 2011.
  * [23] A. McPherson, A. Roth, E. Laks, T. Masud, A. Bashashati, A. W. Zhang, G. Ha, J. Biele, D. Yap, A. Wan, L. M. Prentice, J. Khattra, M. A. Smith, C. B. Nielsen, S. C. Mullaly, S. Kalloger, A. Karnezis, K. Shumansky, C. Siu, J. Rosner, H. L. Chan, J. Ho, N. Melnyk, J. Senz, W. Yang, R. Moore, A. J. Mungall, M. A. Marra, A. Bouchard-Cote, C. B. Gilks, D. G. Huntsman, J. N. McAlpine, S. Aparicio, and S. P. Shah.  Divergent modes of clonal spread and intraperitoneal mixing in high-grade serous ovarian cancer.  Nat Genet, 48(7):758–767, 2016.
  * [24] I. Pe’er, T. Pupko, R. Shamir, and R. Sharan.  Incomplete directed perfect phylogeny.  Siam Journal on Computing, 33(3):590–607, 2004.
  * [25] T. Przytycka, G. Davis, N. Song, and D. Durand.  Graph theoretical insights into evolution of multidomain proteins.  Journal of computational biology, 13(2):351–363, 2006.
  * [26] D. Ringe, T. Warnow, and A. Taylor.  Indo-European and Computational Cladistics.  Transactions of the Philological Society, 100(1):59–129, Mar. 2002\.
  * [27] I. B. Rogozin, Y. I. Wolf, V. N. Babenko, and E. V. Koonin.  Dollo parsimony and the reconstruction of genome evolution.  In I. V. A. Albert, editor, Parsimony, Phylogeny, and Genomics. Oxford University Press, 2006.
  * [28] R. Sedgewick.  Algorithms in C Parts 1-4: Fundamentals Data Structures Sorting Searching.  Algorithms in C. Addison-Wesley, 2001.
  * [29] C. Semple and M. Steel.  Phylogenetics.  Oxford Lecture Series in Mathematics and Its Applications. Oxford University Press, USA, 2003.
  * [30] M. A. Steel.  Phylogeny: discrete and random processes in evolution.  Number 89 in CBMS-NSF regional conference series in applied mathematics. Society for Industrial and Applied Mathematics, Philadelphia, 2016\.
  * [31] J. Zheng, I. B. Rogozin, E. V. Koonin, and T. M. Przytycka.  Support for the Coelomata Clade of Animals from a Rigorous Analysis of the Pattern of Intron Conservation.  Mol. Biol. Evol., 24(11):2583–2592, 2007.

Figure 6: Red-black graph associated with the matrix in Figure 1 and with set
$A=\\{c_{4}\\}$ of active characters, after the realization of the sequence
$\langle c_{3}^{+},c_{5}^{+},c_{2}^{+}\rangle$. The character $c_{2}$ is
adjacent to the species $s_{3},s_{4},s_{5}$ which are all the species in the
same connected components as $c_{2}$. Figure 7: The set of maximal characters
of the red-black graph in Figure 2 is $\\{c_{2},c_{3}\\}$. We represent the
graph $G_{RB}|C_{M}$. Figure 8: The Hasse diagram of the graph of Figure 7,
obtained from the red-black graph $G_{RB}$ of Figure 7. The species $s_{2}$
and $s_{4}$ are two safe sources for $G_{RB}$

(a) Degenerate tree, not in normal form

(b) Degenerate tree, in normal form

(c) Degenerate tree, in normal form

Figure 9: Some possible solutions for a $G_{RB}$ with degenerate Hasse diagram