11institutetext: Université libre de Bruxelles (ULB), Brussels, Belgium
11email<EMAIL_ADDRESS>ETH Zurich, Zürich, Switzerland
22email<EMAIL_ADDRESS>
# Shortest Paths on Polymatroids and Hypergraphic Polytopes

Jean Cardinal 11 0000-0002-2312-0967 Raphael Steiner Research of R.S.
supported by the SNSF Ambizione Grant No. 216071.22 0000-0002-4234-6136

###### Abstract

Base polytopes of polymatroids, also known as generalized permutohedra, are
polytopes whose edges are parallel to a vector of the form
$\mathbf{e}_{i}-\mathbf{e}_{j}$, where the $\\{\mathbf{e}_{i}\\}_{i\in[n]}$
are the canonical basis vectors of $\mathbb{R}^{n}$.

We consider the following computational problem: Given two vertices of a
generalized permutohedron $P$, find a shortest path between them on the
skeleton of $P$, where the length of a path is its number of edges. This
captures many known flip distance problems, such as computing the minimum
number of exchanges between two spanning trees of a graph, the rotation
distance between binary search trees, the flip distance between acyclic
orientations of a graph, or rectangulations of a square.

We prove that this general problem is -hard, even when restricted to very
simple polymatroids in $\mathbb{R}^{n}$ defined by $O(n)$ inequalities.
Assuming $\P\not=\NP$, this rules out the existence of a computationally
efficient simplex pivoting rule that would perform a minimum number of
nondegenerate pivoting steps to an optimal solution of a linear program, even
when the latter defines a polymatroid.

We also prove that the shortest path problem is inapproximable when the
polymatroid is specified via an evaluation oracle for a corresponding
submodular function, which strengthens a recent result by Ito, Kakimura,
Kamiyama, Kobayashi, Maezawa, Nozaki, and Okamoto (ICALP’23). More precisely,
we prove the -hardness of the shortest path problem when the polymatroid is a
hypergraphic polytope, whose vertices are in bijection with acyclic
orientations of a given hypergraph. The shortest path problem then amounts to
computing the flip distance between two acyclic orientations of a hypergraph.

On the positive side, we provide a polynomial-time approximation algorithm for
the problem of computing the flip distance between two acyclic orientations of
a hypergraph, where the approximation factor is the maximum codegree of the
hypergraph. Our result implies in particular an exact polynomial-time
algorithm for the flip distance between two acyclic orientations of any linear
hypergraph.

##  1 Introduction

We consider the problem of finding a shortest path between two vertices of a
graph formed by the vertices and edges of an $n$-dimensional polytope, where
the length of the path is its number of edges. Bounding the length of such
paths has been the topic of intensive research since the birth of the theory
of linear programming and the invention by Dantzig, around 1947, of the
Simplex algorithm, that seeks solutions of a linear program by iteratively
moving from one feasible solution to another, along the edges of the polytope.
The performance of this method, parameterized by a so-called _pivoting rule_ ,
is still the subject of many open questions. In particular, it is not known
whether there exists a pivoting rule that makes the simplex algorithm run in
strongly polynomial time. In a series of recent papers, the question of
whether any efficient algorithm could either find or approximate the shortest
path to a solution has been studied, and several negative results have been
proved [2, 18, 35, 36]. In particular, shortest paths between perfect
matchings of a bipartite graph on the perfect matching polytope were shown to
be hard to approximate [13]. This implies that no simplex pivoting rule can
perform an approximately optimal number of (nondegenerate) pivoting steps,
even on linear programs defined by totally unimodular matrices.

Another motivation for studying shortest paths on polytopes is the problem of
computing the rotation distance between two binary search trees, or,
equivalently, the flip distance between two triangulations of a convex
polygon. The equivalence can be proved by a classical Catalan bijection that
maps every triangulation to its dual tree. This problem, too, can be cast as
finding a shortest path between two vertices of a polytope. The associated
polytope is called the _associahedron_ , and has been the topic of numerous
investigations in various mathematical contexts, including data structures,
topology, and algebra [59, 42, 54, 16]. The complexity status of the rotation
distance problem is another widely open question. It is not known to be -hard,
but no polynomial-time algorithm is known either. The only known results are a
simple polynomial-time 2-approximation algorithm and several polynomial-time
fixed-parameter algorithms [17, 41].

These two problems, the existence of efficient pivoting rules and computing
the rotation distance between binary trees, are our main motivations for
introducing the question of computing the distance between vertices of _base
polytopes of polymatroids_ , also known in the combinatorics literature as
_generalized permutohedra_. In what follows, we will refer to them simply as
_polymatroids_. From the optimization point of view, these are polytopes that
generalize matroid base polytopes, while preserving the property that the
vertices which are extremal with respect to a linear function can be found
easily using a greedy algorithm [58, 22]. Hence just as perfect matching
polytopes, polymatroids yield another class of linear programs that are
solvable in strongly polynomial time. While polymatroids have been introduced
and studied by Edmonds as early as 1970 [21], they play a key role in more
recent developments in algebraic combinatorics, where they are defined as
polytopes whose normal fan is a coarsening of the normal fan of the
permutohedron [52, 53]. They are fundamental objects, among others, in the
study of combinatorial Hopf algebras [1, 40, 45]. Associahedra are classical
examples of polymatroids, hence the rotation distance between binary search
trees is a special case of a shortest path problem on a polymatroid.

Recently, Ito, Kakimura, Kamiyama, Kobayashi, Maezawa, Nozaki, and Okamoto
[35] showed that unless $\P=\NP$, there is no polynomial-time algorithm for
finding a shortest path between two vertices of a polymatroid, when it is
given in the form of an oracle to its associated submodular rank function, a
standard computation model for optimization on matroids and polymatroids. More
precisely, they prove the hardness of computing the rotation distance between
elimination trees on graphs, a problem that generalizes the rotation distance
between binary search trees, and amounts to finding shortest paths on a class
of polymatroids known as _graph associahedra_ [14, 44].

###  1.1 Our results

We strengthen the result by Ito et al. [35] in two ways.

We first show that there exist simply-structured polymatroids in
$\mathbb{R}^{n}$ described by a set of $2n+2$ inequalities, on which the
shortest path problem is strongly -hard. We show that the shortest path
problem on those polytopes is equivalent to the known _pure constant fixed
charge transportation_ problem, a special case of the classical fixed charge
transportation problem.

We then consider the shortest path problem in the setting where the
polymatroid is specified by an oracle to a submodular function. Strengthening
the aforementioned hardness result by Ito et al., we show that in this
computational model, the problem of finding a shortest path between two
vertices of a polymatroid cannot even be efficiently approximated, unless
$\P=\NP$. To prove this result, we consider a special family of polymatroids
defined by acyclic orientations of hypergraphs. These polytopes are known as
_hypergraphic polytopes_ [6, 8]. They form a natural generalization of
polymatroids defined by acyclic orientations of graphs, and have recently been
extensively studied both from an algebraic and combinatorial viewpoint [1,
56]. They also include the special cases of associahedra and graph
associahedra mentioned above.

Finally, we provide a positive result about acyclic orientations of
hypergraphs. We show that the shortest path problem on hypergraphic polytopes
can be approximated within a factor equal to the maximum codegree of the
hypergraph. This provides a new polynomial-time exact algorithm for the
shortest path problem on hypergraphic polytopes corresponding to linear
hypergraphs, i.e. hypergraphs in which any two hyperedges intersect in at most
one vertex.

Section 2 sets the stage for the problems we tackle and details a number of
related computational questions. In Section 3 we prove the hardness of the
shortest path problem on a polymatroid defined by linear inequalities. Section
4 describes the necessary definitions and background related to acyclic
orientations of hypergraphs and the corresponding flip graphs. In Sections 5
and 6, we then present the proofs of the inapproximability result and the
codegree approximation algorithm, respectively.

###  1.2 Other related works

Our contribution is also relevant in the context of _combinatorial
reconfiguration_ problems [33, 30, 25]111See also
https://reconf.wikidot.com/.. In such problems, we are given two combinatorial
objects together with local reconfiguration operations, and we are asked to
decide whether it is possible to transform the first object into the other by
iteratively applying a reconfiguration operation, and if it is, to find the
minimum number of required steps. This problem is typically posed for
structures defined as solutions of optimization problems, such as graph
colorings or dominating sets [47], independent sets [37], cliques [38],
bounded-degree spanning trees [7], $k$-edge-connected orientations [34], among
others. Our results can be seen as contributions in this vein, although in the
cases we consider, the question of whether any two objects are connected is
trivial, since the the polytopal structure ensures connectivity (and in fact,
$d$-connectivity, where $d$ is the dimension of the polytope, from Balinski’s
Theorem [5]).

##  2 Definitions and background

In what follows, we use the notation $\mathbf{p}=(p_{1},p_{2},\ldots,p_{n})$
for $n$-dimensional vectors, and let $[n]:=\\{1,2,\ldots,n\\}$. We first
consider the problem of finding a shortest path between two vertices of a
polytope specified by linear inequalities.

######  Problem 1 (Shortest paths on a polytope)

Given a polytope $P$ in $\mathbb{R}^{n}$, described by a system of linear
inequalities, and two vertices $\mathbf{a}$ and $\mathbf{b}$ of $P$, each
identified by $n$ tight inequalities, find a shortest path from $\mathbf{a}$
to $\mathbf{b}$ on the skeleton of $P$. Here the length of a path is defined
as the number of edges.

This problem is sometimes referred to as _routing_ on a polytope. It is
closely related to the complexity of the Simplex method and the Hirsch
conjecture. In its polynomial version, the latter states that the diameter of
$n$-polytopes with $m$ facets is bounded by a polynomial in $n$ and $m$. If
the polynomial Hirsch conjecture holds, then Problem 1 lies in . It is known
that Problem 1 is -hard to approximate within any constant factor, even when
$P$ is restricted to be the perfect matching polytope of a bipartite graph [2,
13]. We are interested in proving similar results in the case where the
polytope is a polymatroid.

###  2.1 Polymatroids and generalized permutohedra

_Base polytopes of polymatroids_ are also known as _generalized permutohedra_.
In what follows, with a slight abuse of terminology, we will simply refer to
them as _polymatroids_. They can be characterized in different ways [58, 22,
19, 4], generalizing the characterizations of matroid base polytopes by their
edge lengths and the matroid rank function [24, 58].

Recall that a set function $f:2^{[n]}\to\mathbb{R}$ is called _submodular_ if
the inequality $f(T)+f(U)\geq f(T\cap U)+f(T\cup U)$ holds for all pairs $U,T$
of subsets of $[n]$. We let $\mathbf{e}_{i}$ denote the $i$th canonical basis
vector of $\mathbb{R}^{n}$.

######  Theorem 2.1 (Characterizations of polymatroids)

Given a polytope $P\subset\mathbb{R}^{n}$, the following statements are
equivalent:

  1. 1.

Every edge of $P$ is parallel to $\mathbf{e}_{j}-\mathbf{e}_{i}$ for a pair
$i,j\in[n]$.

  2. 2.

There exists a submodular function $f:2^{[n]}\to\mathbb{R}$ such that

$P=P_{f}:=\left\\{\mathbf{x}\in\mathbb{R}^{n}:\sum_{i\in U}x_{i}\leq f(U)\
\mbox{ for all }U\subset[n],\mbox{ and }\sum_{i\in[n]}x_{i}=f([n])\right\\}.$

The reader is referred to [58, 22, 53, 1] for details on this classical
statement. If we further ask the function $f$ to be nondecreasing and satisfy
$f(\emptyset)=0$ and $f(U)\leq|U|$, it is called a _rank function_ , but we
will not require these conditions here. We focus on the case where $f$ only
takes on integral values. In this case the vertices of $P$ have integer
coordinates, hence we focus on _integer polymatroids_.

###  2.2 Shortest paths on polymatroids

We consider a variant of Problem 1 in which the input polytope $P$ is encoded
by a submodular function $f:2^{[n]}\to\mathbb{R}$.

######  Problem 2 (Shortest paths on a polymatroid)

Given an oracle to a submodular function $f$, and two vertices $\mathbf{a}$
and $\mathbf{b}$ of the polytope $P_{f}$, compute the length of a shortest
path from $\mathbf{a}$ to $\mathbf{b}$ on the skeleton of $P_{f}$.

Several interesting computational problems can be reduced to Problem 2.

####  2.2.1 Matroids.

Clearly, when $f$ is the rank function of a _matroid_ $M$ on ground-set $[n]$,
then Problem 2 consists of computing the base exchange distance between two
bases $A$ and $B$ of $M$, which is simply $|A\setminus B|$ (or, symmetrically,
$|B\setminus A|$). In fact, a shortest path between two vertices
$\mathbf{x},\mathbf{y}$ of $P_{f}$ in this case can be found greedily using
polynomially many oracle calls to the rank function $f$: We start by reading
off the corresponding bases $A$ and $B$ as the supports of $\mathbf{x}$ and
$\mathbf{y}$. We then greedily construct a sequence of bases
$A=B_{0},B_{1},\ldots,B_{t}=B$ inducing a shortest path from $\mathbf{x}$ to
$\mathbf{y}$ on $P_{f}$ as follows. For each $k\geq 0$ such that $B\setminus
B_{k}\neq\emptyset$, we search through all potential element-pairs
$(i,j)\in(B\setminus B_{k})\times(B_{k}\setminus B)$ and test whether
$(B_{k}\cup\\{i\\})\setminus\\{j\\}$ is a basis (by using the oracle to decide
if $f((B_{k}\cup\\{i\\})\setminus\\{j\\})=f([n])$). Such a pair always exists
by the basis exchange axiom for matroids. Once a suitable pair $(i,j)$ is
found, we define $B_{k+1}:=(B_{k}\cup\\{i\\})\setminus\\{j\\}$ and proceed.
Thus, Problem 2 is efficiently solvable in the case of matroids.

####  2.2.2 Acyclic orientations of graphs and graphical zonotopes.

Given a simple, connected graph $G=([n],E)$, consider the submodular function
$f:2^{[n]}\rightarrow\mathbb{N}_{0}$, where for a vertex-subset
$U\subseteq[n]$ the value of $f(U)$ is simply defined as the number of edges
that have at least one endpoint in $U$. The polymatroid $P_{f}$ defined by
this choice of $f$ is known as the _graphical zonotope_ of $G$ [60, 26, 27].
The vertices of $P_{f}$ are one-to-one with the acyclic orientations of $G$,
and its edges are one-to-one with pairs of acyclic orientations that differ by
a single edge flip. Given an acyclic orientation $A$ of $G$, the entries of
its corresponding vertex of $P_{f}$ simply correspond to the in-degrees of the
vertices in $A$.

In a way that is similar to the previous case, the flip distance problem for
graphical zonotopes can be shown to be solvable easily: The flip distance
between two acyclic orientations $A$ and $B$ of $G$ is exactly equal to the
number of edges that are oriented differently in $A$ and $B$, and a sequence
of $|A\Delta B|$ edge-reversals that transforms $A$ into $B$ while keeping all
intermediate orientations acyclic can be efficiently computed (see e.g. [23]).
We claim that in fact, a shortest path between two given vertices
$\mathbf{x},\mathbf{y}$ of $P_{f}$ can be found efficiently even when one is
only given oracle access to the function $f$. To see this, note that given any
pair $u,v\in[n]$, we can determine whether $u$ and $v$ are adjacent in $G$ by
computing the value of $f(u)+f(v)-f(\\{u,v\\})$, which is $1$ if $u$ and $v$
are adjacent and $0$ otherwise. Thus, using polynomially oracle calls to $f$
we can determine $G$. Let $A$ and $B$ be the acyclic orientations of $G$ whose
in-degree sequences correspond to $\mathbf{x}$ and $\mathbf{y}$. By repeatedly
identifying a vertex of in-degree $0$ and removing it, we can efficiently
reconstruct the orientations $A$ and $B$ of $G$ from $\mathbf{x}$ and
$\mathbf{y}$. Finally, knowing $A,B$ and $G$ we can efficiently find a
shortest flip-sequence of edge-reversals that transforms $A$ into $B$ (see
[23]) and map this to a shortest path from $\mathbf{x}$ to $\mathbf{y}$ on the
skeleton of $P_{f}$.

We refer the reader to Pilaud [49], and Cardinal, Hoang, Merino, and Mütze [8]
for recent developments on the combinatorics of acyclic orientations of
graphs. One of the contributions of the present paper is the analysis of a
hypergraph generalization of this problem.

####  2.2.3 Triangulations and associahedra.

When the submodular function is defined as

$f(U)=|\\{(i,j)\in[n]^{2}:i<j\mbox{ and }U\cap[i,j]\not=\emptyset\\}|,$ (1)

then the polymatroids are Loday’s associahedra [59, 54, 42, 16, 51]. Problem 2
in this special case is the problem of computing the flip distance between two
triangulations of a convex polygon, where a flip consists of replacing the
diagonal of a quadrilateral formed by two adjacent triangles by its other
diagonal. Equivalently, this amounts to computing the rotation distance
between the dual binary trees. The more general problems of computing flip
distances between triangulations of arbitrary point sets or polygons are known
to be -hard [43, 3]. algorithms have been designed [39, 17].

####  2.2.4 Elimination trees and graph associahedra.

An _elimination tree_ of a graph $G$ is obtained by selecting any vertex $v$
of $G$ as the root, and attaching elimination trees obtained by recursing on
each of the connected component of $G-v$. A natural rotation operation
connects some pairs of elimination trees, and the rotation graph on the
elimination trees is the skeleton of the so-called _graph associahedron_ of
$G$.

The graph associahedron of $G$ can be specified by a submodular function $f$
defined as follows. Let $V$ be the vertex set of $G$, and define
$\mathcal{B}(G)\subset 2^{V}$ as the collection of nonempty subsets
$S\subseteq V$ such that $G[S]$ is connected. The collection $\mathcal{B}(G)$
is known as the _graphical building set_ of $G$. The submodular function
defining the associahedron of $G$ is then defined as

$f(U)=|\\{S\in\mathcal{B}(G):U\cap S\not=\emptyset\\}|.$ (2)

Graph associahedra were defined by Carr and Devadoss [14] and Postnikov [53],
and also considered by Postnikov, Rainer, and Williams [52]. The structure of
their skeleton was the subject of several recent works [44, 9, 10]. The flip
distance problem in this case is known to be -hard from the recent result of
Ito et al. [35].

####  2.2.5 Partial permutations and stellohedra.

Stellohedra are associahedra of stars [44, 15], and their vertices, the
elimination trees of a star, can be shown to be one-to-one with _partial
permutations_ of the set of leaves [9]. The rotations can be interpreted in
that case as either adjacent transpositions or adding or removing an element
in final position. The corresponding flip distance problem was recently shown
to be solvable in polynomial time by Cardinal, Pournin, and Valencia-Pabon
[11].

####  2.2.6 Rectangulations and quotientopes.

A _rectangulation_ is a tesselation of the unit square by disjoint axis-
aligned rectangles. Modulo natural equivalence classes, rectangulations can be
shown to be in bijection with classes of pattern-avoiding permutations [46].
Similarly to triangulations, flip graphs on rectangulations can be defined and
shown to be skeletons of polytopes [12, 45]. These polytopes have been studied
in [40, 55] and belong to the wider family of _quotientopes_ [50, 48]. They
are also polymatroids, and therefore the flip distance problems between
rectangulations are also special cases of Problem 2. The complexity of these
problems is open.

Note that graphical zonotopes, associahedra, graph associahedra, and
stellohedra are all special cases of _hypergraphic polytopes_ , that we
consider extensively in Section 4.

##  3 -hardness of shortest paths on polymatroids defined by linear
inequalities

We prove that Problem 1 is -hard even in the case where the polytope $P$ is a
polymatroid in the sense of Theorem 2.1. In fact, the polytope can be
restricted to be a very special polymatroid.

###### Theorem 3.1

Problem 1 is strongly -hard even when the input polytope is a polymatroid
defined as the intersection of an axis-aligned box with a hyperplane.

We now define precisely the family of polytopes we consider. Let
$\mathbf{a},\mathbf{b}\in\mathbb{N}^{n}$ such that
$\sum_{i=1}^{n}a_{i}=\sum_{i=1}^{n}b_{i}=N$ for some $N\in\mathbb{N}$. In what
follows, we let the vectors $\mathbf{l}$ and $\mathbf{u}$ be defined as
$l_{i}:=\min\\{a_{i},b_{i}\\}$ and $u_{i}:=\max\\{a_{i},b_{i}\\}$,
respectively. We consider the polytope

$P:=\left\\{\mathbf{x}\in\mathbb{R}^{n}:\mathbf{l}\leq\mathbf{x}\leq\mathbf{u}\mbox{
and }\sum_{i=1}^{n}x_{i}=N\right\\}.$

######  Problem 3 (Shortest path on a box)

Given two vectors $\mathbf{a},\mathbf{b}\in\mathbb{N}^{n}$ such that
$\sum_{i=1}^{n}a_{i}=\sum_{i=1}^{n}b_{i}=N$ for some $N\in\mathbb{N}$, and $P$
defined as above, find the shortest path between $\mathbf{a}$ and $\mathbf{b}$
on the skeleton of $P$.

###### Lemma 1

Problem 3 is strongly -hard.

We characterize the edges of $P$ exactly and label them with pairs
$(i,j)\in[n]^{2}$.

###### Lemma 2

Two distinct vertices $\mathbf{x}$ and $\mathbf{y}$ of $P$ are adjacent on the
skeleton of $P$ if and only if there exists two indices $i,j\in[n]$ such that:

  * •

$y_{k}=x_{k}\in\\{l_{k},u_{k}\\}$ for all $k\in[n]$ with $k\not=i,j$,

  * •

$y_{j}=x_{j}+\delta_{ij}$,

  * •

$y_{i}=x_{i}-\delta_{ij}$,

where $\delta_{ij}=\min\\{u_{j}-x_{j},x_{i}-l_{i}\\}$. In that case, we say
that the oriented edge $(\mathbf{x},\mathbf{y})$ is an $(i,j)$-_flip_.

###### Proof

For the first direction of the stated equivalence, suppose that $\mathbf{x}$
and $\mathbf{y}$ are adjacent on the skeleton of $P$. Then the segment
$\operatorname{conv}(\\{\mathbf{x},\mathbf{y}\\})$ forms an edge of $P$ (and
thus, a face of $P$ of dimension $1$). Since $P$ is the intersection of the
axis-aligned box $Q:=[a_{1},b_{1}]\times\cdots\times[a_{n},b_{n}]$ with the
hyperplane $H$ of equation $\sum_{i=1}^{n}x_{i}=N$, it follows that
$\operatorname{conv}(\\{\mathbf{x},\mathbf{y}\\})$ is the intersection of a
two-dimensional face of the box $Q$ and the hyperplane $H$. Such a two-
dimensional face is an axis-aligned rectangle

$R=[l_{i},u_{i}]\times[l_{j},u_{j}]$

lying in a plane orthogonal to all $\mathbf{e}_{k}$ such that $k\not=i,j$. In
this plane, the edge is simply the intersection of $R$ with a line parallel to
$\mathbf{e}_{j}-\mathbf{e}_{i}$. It is straightforward to check that the
coordinates of its endpoints obey the equations above.

Vice-versa, suppose that two distinct vertices $\mathbf{x},\mathbf{y}$ of $P$
satisfy the stated conditions, i.e., there exist $k,\ell\in[n]$ such that
$y_{k}=x_{k}\in\\{u_{k},l_{k}\\}$ for every $k\in[n]\setminus\\{i,j\\}$ and
$y_{j}=x_{j}+\delta_{ij},y_{i}=x_{i}+\delta_{ij}$, where
$\delta_{ij}:=\min\\{u_{j}-x_{j},x_{i}-l_{i}\\}$. We now claim that
$\operatorname{conv}(\\{\mathbf{x},\mathbf{y}\\})$ is a face (and thus an
edge) of $P$, as claimed. To see this, it suffices to note that the face
$F\subseteq P$ defined as

$F=\left\\{z\in\mathbb{R}^{n}\bigg{|}u_{i}\leq z_{i}\leq l_{i},u_{j}\leq
z_{j}\leq l_{j},\forall
k\in[n]\setminus\\{i,j\\}:z_{k}=x_{k},\sum_{i=1}^{N}{z_{i}}=N\right\\}$

contains both $\mathbf{x}$ and $\mathbf{y}$ (and thus
$\operatorname{conv}(\\{\mathbf{x},\mathbf{y}\\})$) and is $1$-dimensional.
This shows that $\mathbf{x},\mathbf{y}$ are adjacent on the skeleton of $P$,
concluding the proof. ∎

From Lemma 2, the edges of $P$ are parallel to $\mathbf{e}_{j}-\mathbf{e}_{i}$
for a pair $i,j\in[n]$. Hence from Theorem 2.1, $P$ is a polymatroid and
Problem 3 can also be reduced to Problem 2. The submodular function
$f:2^{[n]}\to\mathbb{R}$ such that $P_{f}=P$ is

$f(U)=\min\left\\{N-\sum_{i\in[n]\setminus U}l_{i},\sum_{i\in
U}u_{i}\right\\}.$

We say that an $(i,j)$-flip is a _$(U,V)$ -flip_ for some subsets
$U\subseteq[n]$ and $V\subseteq[n]$ if $i\in U$ and $j\in V$. Let
$S:=\\{i\in[n]:a_{i}=u_{i}\\}$, and $T:=\\{i\in[n]:a_{i}=l_{i}\\}=[n]\setminus
S$. The set $S$ is therefore the set of indices of components of $\mathbf{a}$
that have to eventually decrease, while $T$ denote those components that have
to eventually increase.

We show that Problem 3 can be cast as a special case of the _fixed charge
transportation_ problem on the bipartite graph $S\times T$. This problem is a
minimum cost maximum flow problem in which the cost of every edge is the sum
of a variable cost proportional to the flow on the edge and a fixed charge for
each edge with nonzero flow. It has a long history dating back to the
pioneering work from Hirsch and Dantzig [31], and is known to be -hard. The
special case where the cost is simply the number of edges with nonzero flow,
and there is no variable cost, is known as the _pure constant fixed charge
transportation_ (PCFCT) problem. The PCFCT problem has been considered in
particular by Hultberg and Cardoso [32] under the name _teacher assignment
problem_ , and by Schrenk, Finke, and Cung [57]. In a sense, it is about
finding the ”most degenerate” solution to a set of flow and positivity
constraints.

######  Problem 4 (Pure constant fixed charge transportation (PCFCT))

Given two sets $S$ and $T$ and integers $\\{s_{i}\\}_{i\in S}$ and
$\\{t_{i}\\}_{i\in T}$ such that $\sum_{i\in S}s_{i}=\sum_{j\in T}t_{j}$, find
reals $x_{ij}\geq 0$, for $(i,j)\in S\times T$ such that:

$\displaystyle\sum_{j\in T}x_{ij}$ $\displaystyle=$ $\displaystyle s_{i},\
\forall i\in S$ $\displaystyle\sum_{i\in S}x_{ij}$ $\displaystyle=$
$\displaystyle t_{j},\ \forall j\in T,$

and the number of nonzero values $|\\{(i,j)\in S\times T:x_{ij}>0\\}|$ is
minimum.

The PCFCT problem is known to be strongly -hard, see Hultberg and Cardoso
[32]. Their proof is by reduction from the strongly -complete 3-partition
problem. They also observed that the problem can in fact be cast as a maximum
partition problem. We define a _same-sum partition_ of $S$ and $T$ as a
collection of pairs $(S_{\ell},T_{\ell})$ of non-empty subsets of $S$ and $T$,
such that $\\{S_{\ell}\\}$ is a partition of $S$, $\\{T_{\ell}\\}$ is a
partition of $T$, and for each $\ell$, we have $\sum_{i\in
S_{\ell}}s_{i}=\sum_{j\in T_{\ell}}t_{j}$.

######  Lemma 3 (Hultberg and Cardoso [32])

An optimal solution of the PCFCT problem has value $|S|+|T|-m$, where $m$ is
the maximum size of a same-sum partition of $S$ and $T$.

The proof of Lemma 3 is simple. We give an example in Figure 1.

Figure 1: Illustration of Lemma 3. The top and bottom rows show the values of
the $s_{i}$ and $t_{j}$, respectively. There exists a same-sum partition of
size $m=3$, and a corresponding solution of value $|S|+|T|-m=5+5-3=7$.

We now prove the following key lemma, establishing that the PCFCT problem can
be reduced to Problem 3.

###### Lemma 4

Any instance of the PCFCT problem can be converted into an equivalent instance
$(\mathbf{a},\mathbf{b})$ of Problem 3, so that the length of a shortest path
is exactly equal to the value of an optimal solution of the PCFCT instance.

###### Proof

Given an instance $(\\{s_{i}\\}_{i\in S},\\{t_{j}\\}_{j\in T}\\}$ of the PCFCT
problem, we construct an equivalent instance $(\mathbf{a},\mathbf{b})$ of
Problem 3 as follows. First, we can assume without loss of generality that
$S=[n_{1}]$ and $T=\\{n_{1}+1,n_{1}+2,\ldots,n_{1}+n_{2}\\}$, and let
$n=n_{1}+n_{2}$. We now let
$\mathbf{a}=(s_{1},s_{2},\ldots,s_{n_{1}},0,0,\ldots,0)$, and
$\mathbf{b}=(0,0,\ldots,0,t_{1},t_{2},\ldots,t_{n_{2}})$, and $u_{i}=s_{i}$
for each $i\in S$, $u_{j}=t_{j}$ for each $j\in T$, and finally $l_{i}=0$ for
all $i\in S\cup T$.

We first show that given an optimal solution to the PCFCT problem, we can find
a path between $\mathbf{a}$ and $\mathbf{b}$ whose length is the value of the
solution.

Recall from Lemma 3 that an optimal solution can be mapped to a same-sum
partition $(S_{\ell},T_{\ell})_{\ell=1}^{m}$ of $S$ and $T$ of maximum size,
such that the optimal value of the PCFCT equals $|S|+|T|-m$. To construct a
path on the skeleton of $P$ from $\mathbf{a}$ to $\mathbf{b}$ of length
$|S|+|T|-m$, we consider the following simple algorithm.

The algorithm keeps track of two subsets $X$ and $Y$ of $S$ and $T$,
respectively, the current vertex $\mathbf{x}$ of the polytope $P$, as well as
a special “active” element $v$. Initially, the algorithm sets $X\leftarrow
S,Y\leftarrow T$, $\mathbf{x}\leftarrow\mathbf{a}$ and picks $v\in S_{1}$
arbitrarily.

During the process, we maintain the following invariants.

  1. 1.

$\mathbf{x}$ is a vertex of $P$.

  2. 2.

If $\ell$ is the index such that $v\in S_{\ell}\cup T_{\ell}$, then
$X\subseteq S_{\ell}\cup\dots\cup S_{m}$, $Y\subseteq T_{\ell}\cup\dots\cup
T_{m}$ and $v\in X\cap S_{\ell}$ or $v\in Y\cap S_{\ell}$.

  3. 3.

$X=\\{k\in S|x_{k}>0\\}$ and $Y=\\{k\in T|x_{k}<t_{k}\\}$.

  4. 4.

$x_{k}=u_{k}=s_{k}$ for every $k\in X\setminus\\{v\\}$ and $x_{k}=l_{k}=0$ for
every $k\in Y\setminus\\{v\\}$.

  5. 5.

For every $\ell=1,\ldots,m$, it holds that

$\sum_{k\in X\cap S_{\ell}}{x_{k}}=\sum_{k\in Y\cap S_{\ell}}{(t_{k}-x_{k})}.$

Note that these invariants hold after the initialization of
$(\mathbf{x},v,X,y)$. Now, for $\ell=1,\ldots,m$, while $v\in S_{\ell}\cup
T_{\ell}$, the algorithm updates $(\mathbf{x},v,X,y)$ as follows.

It starts by picking a pair $(i,j)\in(X\cap S_{\ell})\times(Y\cap T_{\ell})$
such that $v\in\\{i,j\\}$. Note that this is always possible, since invariants
(2), (3) and (5) together enforce that $X\cap S_{\ell}$ and $Y\cap S_{\ell}$
are non-empty.

The algorithm now performs an $(i,j)$-flip at the vertex $\mathbf{x}$ of $P$
(see the definition from Lemma 2). Concretely, we put
$\delta\leftarrow\min\\{x_{i},t_{j}-x_{j}\\}$ and update $x_{i}\leftarrow
x_{i}-\delta,x_{j}\leftarrow x_{j}+\delta$. Since $x_{k}\in\\{l_{k},u_{k}\\}$
for every $k\notin\\{i,j\\}$ by the invariants (3) and (4), Lemma 2 shows that
this change of $\mathbf{x}$ indeed corresponds to moving along an edge of the
polytope $P$, in particular invariant (1) is preserved. Note that by
definition of $\delta$, we have $x_{i}=0$ or $x_{j}=l_{j}=t_{j}$ after the
flip. The algorithm now proceeds according to the following cases:

  * •

If $x_{i}=0$ and $x_{j}<t_{j}$ after the flip, then the algorithm updates
$X\leftarrow X\setminus\\{i\\}$ and $v\leftarrow j$.

  * •

Symmetrically, if $x_{i}>0$ and $x_{j}=t_{j}$ after the flip, then the
algorithm updates $Y\leftarrow Y\setminus\\{j\\}$ and $v\leftarrow i$.

  * •

If $x_{i}=0$ and $x_{j}=t_{j}$ after the flip, then we claim that we must have
$X\cap S_{\ell}=\\{i\\}$ and $Y\cap S_{\ell}=\\{j\\}$. Indeed, if $x_{i}=0$
and $x_{j}=t_{j}$ after the flip, then we must have had $x_{i}=t_{j}-x_{j}$
before the flip. Using invariant (5), this implies

$\sum_{k\in(X\cap S_{\ell})\setminus\\{i\\}}{x_{k}}=\sum_{k\in(Y\cap
S_{\ell})\setminus\\{j\\}}{(t_{k}-x_{k})}.$

However, by invariant (4) we have $x_{k}=s_{k}$ for every $k\in(X\cap
S_{\ell})\setminus\\{i\\}$ and $x_{k}=0$ for every $k\in(Y\cap
S_{\ell})\setminus\\{j\\}$. This implies that refining the same-sum partition
of $(S,T)$ by replacing the pair $(S_{\ell},T_{\ell})$ with the two pairs
$((X\cap S_{\ell})\setminus\\{i\\},(X\cap S_{\ell})\setminus\\{j\\})$ and
$((S_{\ell}\setminus X)\cup\\{i\\},(T_{\ell}\setminus Y)\cup\\{j\\})$ would
yield a larger same-sum partition, a contradiction — unless $(X\cap
S_{\ell})\setminus\\{i\\}$ and $(Y\cap T_{\ell})\setminus\\{j\\}$ are empty.
This proves that $X\cap S_{\ell}=\\{i\\}$ and $Y\cap S_{\ell}=\\{j\\}$, as
claimed above.

Finally, the algorithm proceeds to update $X\leftarrow
X\setminus\\{i\\},Y\leftarrow Y\setminus\\{j\\}$. If $\ell<m$, then it updates
$v$ to be any vertex of $S_{\ell+1}$, and the for loop now continues with the
new index $\ell+1$ instead of $\ell$. If $\ell=m$, then the algorithm stops
and returns the sequence of all vertices of $P$ visited during the process.

Pause to note that each of the three types of updates above preserve our
invariants (1)–(5). It is clear from the above update rules that in every step
of the algorithm, whenever we take a step along an edge of $P$ to a new
vertex, the value of $|X|+|Y|$ decreases by one, and in fact sometimes this
value decreases by two, namely exactly once in each of the $m$ iterations of
the for loop, when we depart the while-loop for a fixed $\ell=1,\ldots,m$ and
make the intersection of $X$ and $Y$ with $S_{\ell}$ and $T_{\ell}$ empty.

The above implies that the algorithm finishes after a total of $|S|+|T|-m$
steps, and returns a sequence of $|S|+|T|-m+1$ vertices of $P$, any two
consecutive of which are adjacent on the skeleton. Note that at each point of
the algorithm, by invariant (3) it holds that $|X|+|Y|$ is the hamming-
distance between the current vertex $\mathbf{x}$ of $P$ and the target-vertex
$\mathbf{b}$. In particular, the last vertex of this sequence is equal to
$\mathbf{b}$. It follows that the sequence of vertices of $P$ that we output
forms a path from $\mathbf{a}$ to $\mathbf{b}$ on the skeleton of $P$ that has
length $|S|+|T|-m$, as desired. This concludes the first part of the proof of
the lemma.

We now turn to the second part of the proof, and show that given a path
between $\mathbf{a}$ and $\mathbf{b}$ on the skeleton of $P$, we can find a
solution of the PCFCT instance whose value is at most the length of the path.
Let us consider all flips on this path, and construct the undirected graph $G$
on $S\cup T$ in which two vertices $i,j$ are adjacent whenever there is an
$(i,j)$-flip in the path. Note that some flips might not be $(S,T)$-flips, so
$G$ is not necessarily bipartite. Each connected component $S_{\ell}\cup
T_{\ell}$ of $G$ must be such that $\sum_{i\in S_{\ell}}s_{i}=\sum_{j\in
T_{\ell}}t_{j}$. Hence the connected components induce a same-sum partition of
$S$ and $T$, of some size $m$. So from Lemma 3, we can construct a solution of
the PCFCT problem of value $|S|+|T|-m=n-m$. On the other hand, the number of
flips in each connected component $S_{\ell}\cup T_{\ell}$ of $G$ is at least
$|S_{\ell}|+|T_{\ell}|-1$, hence the total number of flips on the path is at
least $\sum_{\ell=1}^{m}(|S_{\ell}|+|T_{\ell}|-1)=n-m$.∎

Combining Lemma 4 with the fact that the PCFCT problem is strongly -hard
proves Lemma 1, and therefore Theorem 3.1.

##  4 Flip distances between acyclic orientations of hypergraphs

We introduce hypergraphic polytopes, the associated flip distance problem, and
our two results on the complexity of this problem: an -hardness proof, and an
approximation algorithm.

###  4.1 Hypergraphic polytopes

Every hypergraph $H=(V,\mathcal{E})$, where $\mathcal{E}\subseteq
2^{V}\setminus\\{\emptyset\\}$, induces a corresponding submodular function
$f_{H}$ according to

$f_{H}(U):=|\\{e\in\mathcal{E}:U\cap e\not=\emptyset\\}|$ (3)

for every $U\subseteq V$. The base polytope induced by the polymatroid
associated with $f_{H}$ is then called the _hypergraphic polytope_ of the
hypergraph $H$, and denoted by $P_{H}$. Hypergraphic polytopes and the
corresponding polymatroids have been studied in various guises in the past 50
years as covering hypermatroids [29], Boolean polymatroids [61], or relational
submodular functions [1]. Hypergraphic polytopes form an important family of
generalized permutohedra [52, 53, 1, 56].

Interestingly, this definition encompasses most of the special cases we
described in Section 2.2. When $H$ is a graph, the polymatroids are the
graphical zonotopes, whose vertices are in bijection with acyclic orientations
of the graph. When $H$ is defined as

$H=\\{\\{i,i+1,\ldots,j-1,j\\}:1\leq i<j\leq n\\},$

then one can check that Eqn. 3 matches Eqn. 1, hence the hypergraphic polytope
is nothing but the associahedron. When the hyperedges correspond with building
sets of some graph $G$, then the definition matches that of Eqn. 2, and the
polymatroid is a graph associahedron. We refer to [52, 53, 6, 56, 8] for
detailed treatments of the connections of the polytopes $P_{H}$ to
combinatorial structures.

###  4.2 Acyclic orientations of hypergraphs

It is known that the vertices of the hypergraphic polytope $P_{H}$ are in one-
to-one correspondence with so-called _acyclic orientations_ of the hypergraph
$H$ [6, 56, 8], which we define now.

An _orientation_ of a hypergraph $H=(V,\mathcal{E})$ is a mapping
$h:\mathcal{E}\rightarrow V$ such that $h(e)\in e$ for every
$e\in\mathcal{E}$. The element $h(e)$ is also called the _head_ of an edge
$e$. With every orientation $h$ of $H$ we can associate a directed graph
$D_{h}$ that has vertex set $h$ and an arc from a vertex $u$ to a vertex $v$
if and only if there exists some $e\in\mathcal{E}$ such that $h(e)=v$ and
$u\in e\setminus\\{v\\}$. Intuitively, $D_{h}$ is the union, over all
$e\in\mathcal{E}$, of the inwards-oriented stars centered at the head of $e$
and whose leaves are all other elements of $e$. With this notion at hand, we
call an orientation $h$ of $H$ _acyclic_ if $D_{h}$ is an acyclic digraph.

Figure 2: An example of flip, showing all hyperedges $e\in\mathcal{E}$ such
that $e\supseteq\\{u,v\\}$ and satisfying $h_{1}(e)=u$, and arrows pointing to
their heads $h_{1}(e)$ (left) and $h_{2}(e)$ (right). The bottom figure shows
the corresponding parts of the digraphs $D_{h_{1}}$ and $D_{h_{2}}$.

Adjacency of vertices on the skeleton of $P_{H}$ has also been characterized,
see Theorem 4.1 below. In order to state it, we need one more definition,
which is that of a _flip_. Given two distinct acyclic orientations $h_{1}$,
$h_{2}$ of a hypergraph $H=(V,\mathcal{E})$, we say that $h_{2}$ is obtained
from $h_{1}$ by a _flip_ at an ordered pair $(u,v)\in V^{2}$ of distinct
vertices, if $h_{2}$ is obtained from $h_{1}$ by redefining the head of every
hyperedge $e\in\mathcal{E}$ with $e\supseteq\\{u,v\\}$ that satisfies
$h_{1}(e)=u$ as $h_{2}(e)=v$, while keeping all other head assignments the
same as in $h_{1}$. We note that the above definition of a flip is symmetric,
in the following sense: If $h_{2}$ can be obtained from $h_{1}$ by flipping at
$(u,v)$, then $h_{1}$ is obtained from $h_{2}$ by flipping at $(v,u)$. Also,
note that when $h_{2}$ is obtained from $h_{1}$ by flipping at $(u,v)$, then a
flip at $(v,u)$ for $h_{1}$ is impossible. Thus, in the following we can say
without ambiguity that two acyclic orientations $h_{1}$ and $h_{2}$ are
obtained from each other by flipping the unordered pair $\\{u,v\\}$ of
distinct vertices if $h_{2}$ can be obtained from $h_{1}$ by flipping $(u,v)$
or $(v,u)$. An illustration is given in Figure 2

The following statement can be deduced as a special case of Theorem 2.18 in
[6].

###### Theorem 4.1

Let $H=(V,\mathcal{E})$ be a hypergraph. Two vertices $x,y$ of the polytope
$P_{H}$ corresponding to acyclic orientations $h_{1},h_{2}$ of $H$ are
adjacent on the skeleton of $P_{H}$ if and only if there exists a pair
$\\{u,v\\}\subseteq V$ of distinct vertices such that $h_{1}$ and $h_{2}$ can
be obtained from each other by flipping $\\{u,v\\}$.

###  4.3 Flip distances between acyclic orientations of hypergraphs

Theorem 4.1 implies that the computation of shortest paths on the skeleton of
a hypergraphic polytope $P_{H}$ boils down to a flip distance problem between
acyclic orientations of $H$, as follows:

###### Problem 5

Given a hypergraph $H=(V,\mathcal{E})$ and two acyclic orientations
$h_{1},h_{2}$ of $H$ as input, find a shortest sequence vertex-pairs
$\\{u_{i},v_{i}\\}$, $i=1,\ldots,\ell$ such that $h_{2}$ can be obtained from
$h_{1}$ by flipping, in order,
$\\{u_{1},v_{1}\\},\ldots,\\{u_{\ell},v_{\ell}\\}$.

Problem 5 generalizes several of the previous problems mentioned in Section 2.
It clearly includes the special case of flip distances between acyclic
orientations of graphs, when the hypergraph $H$ is a graph. The flip distance
between triangulations or binary search trees is the special case of Problem 5
in which the underlying hypergraph is the set of intervals in $[n]$, as
mentioned above.

In the following, we will prove several results regarding the computational
complexity of Problem 5. On the negative side, we show that approximating the
length of a shortest flip sequence between two acyclic orientations of a
general hypergraph $H$ is -hard, even restricted to hypergraphs $H$ of bounded
degree and bounded hyperedge size.

###### Theorem 4.2

There exists an absolute constant $\Delta\in\mathbb{N}$ such that Problem 5 is
-hard even when the input hypergraph $H=(V,\mathcal{E})$ is known to have
maximum degree at most $\Delta$ and be such that $|e|\leq 3$ for every
$e\in\mathcal{E}$.

The proof of Theorem 4.2 is given in Section 5. Since the input hypergraph $H$
allows to compute the submodular function associated with $H$ efficiently,
Theorem 4.2 implies the following.

###### Corollary 1

There exists a constant $\varepsilon>0$ such that Problem 2 cannot be
approximated to within a factor $(1+\varepsilon)$ in polynomial time, unless
$\P=\NP$.

On the positive side, we prove that shortest paths in the skeleton of $P_{H}$
can be approximated efficiently up to a multiplicative factor that is bounded
by the _maximum codegree_ in $H$. Given a hypergraph $H=(V,\mathcal{E})$ and a
pair $\\{u,v\\}$ of distinct vertices, the _codegree_ of $\\{u,v\\}$ is
defined as

$\text{codeg}(\\{u,v\\}):=|\\{e\in\mathcal{E}|\\{u,v\\}\subseteq e\\}|,$

and the maximum codegree of $H$ is defined as

$\Delta_{2}(H):=\max\\{\text{codeg}(\\{u,v\\})|u\neq v\in V\\}.$

###### Theorem 4.3

There exists a polynomial-time algorithm that, given as input a hypergraph $H$
and two acyclic orientations $h_{1},h_{2}$ of $H$, outputs a flip sequence
$\\{u_{1},v_{1}\\},\ldots,\\{u_{\ell},v_{\ell}\\}$ from $h_{1}$ to $h_{2}$
such that $\ell\leq\Delta_{2}(H)\cdot\text{dist}(h_{1},h_{2})$, where
$\text{dist}(h_{1},h_{2})$ denotes the length of a shortest flip sequence from
$h_{1}$ to $h_{2}$.

In particular, for _linear hypergraphs_ , these are the hypergraphs
$H=(V,\mathcal{E})$ satisfying $|e_{1}\cap e_{2}|\leq 1$ for every distinct
$e_{1},e_{2}\in\mathcal{E}$, we obtain an efficient precise algorithm for
computing a shortest flip sequence between two acylic orientations.

###### Corollary 2

There exists a polynomial-time algorithm that, given as input a linear
hypergraph $H$ and two acyclic orientations $h_{1},h_{2}$ of $H$, outputs a
shortest flip-sequence from $h_{1}$ to $h_{2}$.

The proof of Theorem 4.3 is given in Section 6.

##  5 Proof of Theorem 4.2

Our proof describes a reduction from the minimum vertex cover problem in
graphs, which is well-known to be -hard. Recall that a vertex cover of a graph
$G=(V,E)$ is a subset $X\subseteq V$ such that every edge $e\in E$ has at
least one endpoint in $X$.

We use the following classical hardness result due to Håstad [28]. While
Håstad only stated hardness of approximation on general graphs, his result in
fact applies to bounded-degree graphs, see for instance [20], page 449 for an
explanation why we can restrict Theorem 5.1 to the bounded-degree case.

######  Theorem 5.1 ([28])

There exists an absolute constant $\Delta>0$ such that the following holds.
Unless ¶$=$, there exists no polynomial-time algorithm that achieves an
approximation ratio of less than $7/6$ for the following minimization problem.

Input: A graph $G=(V,E)$ of maximum degree at most $\Delta$.

Output: The size $|X|$ of a smallest vertex cover $X\subseteq V$ of $G$.

Before proceeding to the proof of Theorem 4.2, we describe a hypergraph that
will be used as a gadget in our reduction. This gadget exploits the fact that
stellohedra do not have the non-leaving face property [44, 15]. The way this
gadget is used in the reduction is inspired by previous reductions for the
flip distance problem in geometric triangulations [3, 43].

The _star gadget_ is the hypergraph $S=(V,\mathcal{E})$, where
$V=\\{0,1,\ldots,6\\}$ and
$\mathcal{E}=\\{\\{0,i\\}:i\in[6]\\}\cup\\{\\{0,i,j\\}:i,j\in[6],i\not=j\\}$.
Hence it is composed of a star graph, together with all triples of vertices
containing exactly two leaves of the star. The vertex 0 will be called the
_center_ of the star gadget, and the vertices in $[6]$ will be referred to as
the _leaves_.

We define two orientations $h_{1}$ and $h_{2}$ of the star gadget. In both
orientations, all hyperedges of the form $e=\\{0,i\\}$ are such that
$h_{1}(e)=h_{2}(e)=i$. On the other hand, for hyperedges of the form
$e=\\{0,i,j\\}$, we let $h_{1}(e)=\min\\{i,j\\}$, and
$h_{2}(e)=\max\\{i,j\\}$.

Figure 3: Twelve flips are sufficient to transform $h_{1}$ (left) into $h_{2}$
(right). The transitive reductions of the orientations are shown at each step,
each of which is a broom, composed of a handle – a chain above vertex 0 – and
a collection of independent vertices below 0.

###### Lemma 5

The flip distance between the two orientations $h_{1}$ and $h_{2}$ of the star
gadget is 12. However, any sequence of flips between $h_{1}$ and $h_{2}$ that
does not involve the vertex 0 has length at least 15.

###### Proof

We observe that the acyclic orientations of the star gadget $S$ are one-to-one
with _brooms_ , as pictured in Figure 3. Given an acyclic orientation $h$, let
$W\subseteq[6]$ be the set of vertices $i$ whose edge $e=\\{0,i\\}$ is such
that $h(e)=i$. Consider the transitive reduction $D$ of the digraph $D_{h}$.
Then $D$ consists of two parts: A directed path, that we call the _handle_ ,
originating from 0 and involving vertices of $W$, and a directed star of
center 0 with leaves consisting the vertices not in $W$, all pointing to 0.
Indeed, the hyperedges of the form $e=\\{0,i,j\\}$ induce a total order on
$W$, while the other vertices are incomparable in $D$.

The orientations $h_{1}$ and $h_{2}$ are both such that the set $W$ contains
all 6 vertices, but the order in the handle is reversed. There is a sequence
of 12 flips that transforms $h_{1}$ into $h_{2}$. It consists of iteratively
removing each of the 6 vertices from the handle of the broom, by performing
the 6 flips $\\{0,6\\},\\{0,5\\},\ldots,\\{0,1\\}$, then the same flips again,
in the same order: $\\{0,6\\},\\{0,5\\},\ldots,\\{0,1\\}$ (see Figure 3).

On the other hand, if we are not allowed to flip any pair of the form
$\\{0,i\\}$, we can only change the order of two adjacent vertices in the
handle, by flipping a pair $\\{i,j\\}$ with $i,j>0$. This amounts to transform
the identity permutation on 6 elements into the reverse identity permutation
by adjacent transpositions. Since all pairs are reversed, this costs
${6\choose 2}=15$ flips.∎

Figure 4: Illustration of the proof of Theorem 4.2. Given an instance $G$ of
the vertex cover problem on the left, we construct the hypergraph $H$ on the
right (we omit the depiction of the 3-edges within each of the star gadgets).

######  Proof (Theorem 4.2)

Consider an instance $G=(V,E)$ of the minimum vertex cover problem, with
$|V|=n$ and $|E|=m$ and maximum degree bounded by a absolute constant
$\Delta$. We construct a hypergraph $H=(V^{\prime},\mathcal{E})$ as follows.
First, we choose and fix some linear ordering $(V,\prec)$ of the vertex-set of
$G$. Next, for each vertex $v\in V$, we construct two vertices $v^{-}$ and
$v^{+}$ in $V^{\prime}$, and connect them by an edge $\\{v^{-},v^{+}\\}$ in
$\mathcal{E}$. Then, for each edge $e=\\{u,v\\}\in E$ such that $u\prec v$, we
include the following vertices and hyperedges in the hypergraph $H$:

  1. 1.

A copy $S_{e}$ of the star gadget,

  2. 2.

an edge connecting the center of the star $S_{e}$ to $u^{-}$,

  3. 3.

the edge $\\{u^{+},v^{-}\\}$,

  4. 4.

6 edges connecting $v^{+}$ to each of the leaves of $S_{e}$.

The hypergraph $H$ has $|V^{\prime}|=2n+7m$ vertices and $|\mathcal{E}|=n+29m$
hyperedges. An illustration is given in Figure 4.

We now consider two orientations $h_{1}$ and $h_{2}$ of $H$. In both
orientations, for each vertex $v\in V$, the edge $\\{v^{-},v^{+}\\}$ is
oriented from $v^{-}$ to $v^{+}$, and for each edge $e=\\{u,v\\}\in E$, the
edges of $H$ of type 2 above are oriented from the center of $S_{e}$ to
$u^{-}$, the edges of type 3 are oriented from $u^{+}$ to $v^{-}$, and the
edges of type 4 are oriented towards the leaves of $S_{e}$. Also, for each
star gadget, all hyperedges of size two are oriented towards the leafs. The
only difference between $h_{1}$ and $h_{2}$ are the orientations of the
hyperedges of size three of the star gadgets. For each such hyperedge of the
form $t=\\{0,i,j\\}$, we set $h_{1}(e)=\min\\{i,j\\}$, and
$h_{2}(e)=\max\\{i,j\\}$.

###### Claim

The orientations $h_{1}$ and $h_{2}$ are acyclic.

###### Proof

To certify that the digraphs $D_{h_{1}}$ and $D_{h_{2}}$ corresponding to the
orientations $h_{1},h_{2}$ of $H$ are indeed acyclic, we will describe two
linear oderings of $V^{\prime}$ that are _topological orderings_ , i.e., all
directed edges in $D_{h_{1}}$ (or, $D_{h_{2}}$, respectively) have the
property that their starting point precedes their endpoint in the ordering.

In both orderings, for $D_{h_{1}}$ and $D_{h_{2}}$, we start by listing all
the $0$-vertices of all the star-gadgets $S_{e}$ for all $e\in E$. Note that
these vertices form an independent set in both $D_{h_{1}}$ and $D_{h_{2}}$.
Then, we start by listing the pairs of vertices $v^{-},v^{+}$ (in this order)
for all $v\in V$, where we order the pairs according to the linear order
$\prec$ that we initially fixed on $V$. The latter makes sure that all the
edges directed from $u^{+}$ to $v^{-}$ for some edge $\\{u,v\\}\in E$ with
$u\prec v$ are indeed going forward in the linear ordering we define on
$V^{\prime}$. At the end of the ordering, we list all the vertices that are
leafs of some star $S_{e},e\in E$. While it does not matter in which order we
put the leaves of different stars, it is crucial that within each of the
stars, we order the leaves in decreasing order (i.e. $6,5,\ldots,1$) for the
orientation $D_{h_{1}}$ and in the opposite order (i.e. $1,2,\ldots,6$) for
the orientation $D_{h_{2}}$. It is not hard to check by going through all
directed edges of $D_{h_{1}}$ and $D_{h_{2}}$ that both of these orderings for
$D_{h_{1}}$ and $D_{h_{2}}$ are indeed topological, concluding the proof.∎

This finishes the description of our instance of the flip distance problem,
composed of $H$ together with its two acyclic orientations $h_{1}$ and
$h_{2}$.

Let us denote by $x$ the size of a minimum vertex cover of $G$. We now prove
the following:

###### Claim

The length of a shortest flip sequence between $h_{1}$ and $h_{2}$ is equal to

$2x+12m.$

###### Proof

We first show that there exists a flip sequence transforming $h_{1}$ into
$h_{2}$, of length at most $2x+12m$. First observe that all edges of $H$ of
the form $\\{v^{-},v^{+}\\}$ can be flipped independently, without affecting
acyclicity (indeed, in the topological ordering of $V^{\prime}$ for
$D_{h_{1}}$ described in the proof of the previous claim, one may just flip
the order in which $v^{-}$ and $v^{+}$ occur for every $v\in X$, and the
arising ordering is still topological). Now pick a minimum vertex cover
$X\subseteq V$ of $G$, and flip all edges of the form $\\{v^{+},v^{-}\\},v\in
X$. This needs $x$ flips.

We now observe that after these flips, no directed path in the associated
digraph leaves and goes back to a star gadget. Indeed, consider any star
gadget $S_{e}$ corresponding to an edge $e=uw$ of $G$ with $u\prec w$. Then
$u\in X$ or $w\in X$. This means that in the orientation of $H$ obtained after
flipping all pairs $\\{v^{+},v^{-}\\},v\in X$ we have that $u^{-}$ is a sink
(if $u\in X$) or $w^{+}$ is a source (if $w\in X$). In the first case, every
directed path leaving $S_{e}$ at its center must end already at $u^{-}$ and
thus cannot return to $S_{e}$, and in the second case, every directed path
entering $S_{e}$ at one of its leaves must begin already at $w^{+}$ and thhus
could not have started in $S_{e}$.

Hence all star gadgets can now be flipped independently from the rest of the
hypergraph, without creating new directed cycles in the digraphs corresponding
to the orientations. We next flip all star gadgets using exactly 12 flips per
gadget, as described in Lemma 5. Finally, we can flip back all edges
$\\{v^{-},v^{+}\\}$ for $v\in X$. By the same arguments as above, these flips
do not affect acyclicity. The total length of the described flip sequence is
$2x+12m$.

We now show that any flip sequence transforming $h_{1}$ into $h_{2}$ must have
length at least $2x+12m$. Consider such a flip sequence of length $\ell$, and
let $R$ be the set of edges $ab$ of size two of $H$, excluding the edges of
the star gadgets, such that the pair $\\{a,b\\}$ occurs in the flip sequence
from $h_{1}$ and $h_{2}$. Since the orientations $h_{1}$ and $h_{2}$ agree on
these edges, and since they are not included in any larger hyperedges of $H$,
the flip sequence must flip each such pair at least twice. So in total the
flip sequence involves at least $2|R|$ such flips. We let $r=|R|$.

We now partition the set $E$ of edges of $G$ into two subsets. For each edge
$e=\\{u,v\\}\in E$ with $u\prec v$, consider the (six) paths from the center
of $S_{e}$ to a leaf of $S_{e}$, and going through the vertices
$u^{-},u^{+},v^{-}$, and $v^{+}$. We now denote by $E_{1}\subseteq E$ the set
of edges $e\in E$ such that no edge of any of these six paths is included in
$R$, and let $E_{2}=E\setminus E_{1}$.

From Lemma 5, each star gadget $S_{e}$ requires 15 flips if $e\in E_{1}$,
since in that case any flip involving the center of the star would create a
directed cycle with one of the paths associated with $e$, and thus the edges
of size $2$ in $S_{e}$ can never be flipped in this case. On the other hand,
if $e\in E_{2}$, we know that the star gadget requires at least 12 flips.

Therefore the total length of the flip sequence satisfies

$\ell\geq 15|E_{1}|+12|E_{2}|+2r.$

We now observe that

$x\leq r+|E_{1}|.$ (4)

Indeed, define a set $W\subseteq V$ of vertices as follows: We put $w\in W$ if
and only if one of the edges that connect a center of a star gadget to $w^{-}$
is in $R$, or if $w^{+}$ is incident to an edge in $R$. It is straightfoward
to check that for every edge $e\in E_{2}$, at least one of its endpoints is in
$W$. Pause to note that $|W|\leq|R|=r$. Thus, adding to $W$ for each edge
$e\in E_{1}$ one of its endpoints, we obtain a vertex cover of $G$, which is
of size at most $r+|E_{1}|$.

It remains to bound $\ell$ as follows:

$\displaystyle\ell$ $\displaystyle\geq$ $\displaystyle 15|E_{1}|+12|E_{2}|+2r$
$\displaystyle=$ $\displaystyle 15|E_{1}|+12(m-|E_{1}|)+2r$
$\displaystyle\geq$ $\displaystyle 2|E_{1}|+12m+2r$ $\displaystyle\geq$
$\displaystyle 2(x-r)+12m+2r\text{\ (from\ Eq. }\eqref{eq:xbound}\text{)}$
$\displaystyle=$ $\displaystyle 2x+12m.$

This concludes the proof of the claim.∎

To finish the proof, we need to show that if there exists a
$(1+\varepsilon)$-approximation of the flip distance between $h_{1}$ and
$h_{2}$, then we can obtain a $(1+\delta)$-approximation of the size of a
minimum vertex-cover of $G$, where $\delta=\delta(\varepsilon)$ tends to $0$
with $\varepsilon$. Let $d$ form a $(1+\varepsilon)$-approximation of the flip
distance. Note that by the definition of a vertex-cover, it holds that
$m=|E|\leq\Delta x$. We have

$2x+12m\leq d\leq(1+\varepsilon)(2x+12m).$

Hence

$\displaystyle x$ $\displaystyle\leq$ $\displaystyle\frac{1}{2}(d-12m)$
$\displaystyle\leq$ $\displaystyle\frac{1}{2}((1+\varepsilon)(2x+12m)-12m)$
$\displaystyle=$ $\displaystyle(1+\varepsilon)x+6\varepsilon m$
$\displaystyle\leq$ $\displaystyle(1+\varepsilon+6\varepsilon\Delta)x,$

so $\frac{d-12m}{2}$ forms a $(1+\delta)$-approximation for $x$ where
$\delta(\varepsilon)=(1+6\Delta)\varepsilon=O(\varepsilon)$. ∎

##  6 Proof of Theorem 4.3

We now prove Theorem 4.3. At the heart of our proof is the following key
lemma, which we show first.

###### Lemma 6

Let $H=(V,\mathcal{E})$ be a hypergraph and let $h_{1},h_{2}$ be distinct
acyclic orientations of $H$. Then there exists $e\in\mathcal{E}$ such that
$h_{1}(e)\neq h_{2}(e)$ and $(h_{1}(e),h_{2}(e))$ is flippable in $h_{1}$.

###### Proof

Let $\mathcal{E}^{\prime}:=\\{e\in\mathcal{E}|h_{1}(e)\neq h_{2}(e)\\}$.
Towards a contradiction, suppose that for every edge
$e\in\mathcal{E}^{\prime}$, the pair $(h_{1}(e),h_{2}(e))$ is not flippable in
$h_{1}$. By definition, this means that for every $e\in\mathcal{E}^{\prime}$
there exists a directed cycle in the digraph $D_{h^{e}}$, where
$h^{e}:\mathcal{E}\rightarrow V$ denotes the orientation of $H$ defined by

$h^{e}(f):=\begin{cases}h_{2}(e),&\text{ if }h_{1}(f)=h_{1}(e)\text{ and
}\\{h_{1}(e),h_{2}(e)\\}\subseteq f\\\ h_{1}(f),&\text{ otherwise}\end{cases}$

for every $f\in\mathcal{E}$. In the following, we denote by $D\subseteq
D_{h_{1}}$ the _transitive reduction_ of $D_{h_{1}}$. Our first claim below is
illustrated on Figure 5.

Figure 5: Illustration of the first claim in the proof of Lemma 6. The figure
on the right illustrates the case where $h_{2}(e)=h_{2}(e^{\prime})$ and $a$
is the first arc of $Q$.

###### Claim

For every $e\in\mathcal{E}^{\prime}$, there exists some
$e^{\prime}\in\mathcal{E}^{\prime}$ and a directed path $Q$ in $D$ starting at
$h_{2}(e)$ and ending at $h_{1}(e)$, such that the following statements hold:

  1. 1.

$Q$ has length at least two.

  2. 2.

There exists an arc $a=(x,y)$ on $Q$, such that $x,y\in e^{\prime}$ and
$h_{1}(e^{\prime})=y$.

  3. 3.

The path $W$ composed of the prefix of $Q$ from $h_{2}(e)$ to $x$ followed by
the arc $(x,h_{2}(e^{\prime}))$ (if $x\not=h_{2}(e^{\prime})$) is a directed
path in $D_{h_{2}}$. It is of length at least one unless
$h_{2}(e)=h_{2}(e^{\prime})$ and $a$ is the first arc of $Q$.

###### Proof

Let $C$ be a shortest directed cycle in $D_{h^{e}}$. Then $C$ must use at
least one arc of the form $(z,h_{2}(e))$ for some vertex $z\in f$ and
$f\in\mathcal{E}$ with $\\{h_{1}(e),h_{2}(e)\\}\subseteq f$,
$h_{1}(f)=h_{1}(e)$ and $h^{e}(f)=h_{2}(e)$. Also, note that if $z=h_{1}(e)$,
then $C$ must have length at least three, since $(h_{2}(e),h_{1}(e))$ cannot
be an arc of $D_{h^{e}}$. Observe that the directed path $P:=C-(z,h_{2}(e))$
in $D_{h^{e}}$ also forms a directed path from $h_{2}(e)$ to $z$ in the
digraph $D_{h_{1}}$. Now consider the path $P^{\prime}$ in $D_{h_{1}}$,
defined as $P^{\prime}:=P$ if $z=h_{1}(e)$, and as
$P^{\prime}:=P+(z,h_{1}(e))$ if $z\neq h_{1}(e)$. Then $P^{\prime}$ is a
directed path in $D_{h_{1}}$ from $h_{2}(e)$ to $h_{1}(e)$. Since $C$ has
length at least three if $z=h_{1}(e)$, $P^{\prime}$ must have length at least
two.

This proves that there is a directed path of length at least two in
$D_{h_{1}}$ from $h_{2}(e)$ to $h_{1}(e)$. Let us now define $Q$ as a longest
directed path in $D_{h_{1}}$ from $h_{2}(e)$ to $h_{1}(e)$. Then $Q$ also has
length at least two, and the first item of the claim holds. Furthermore, the
maximality of $Q$ implies that $Q$ is fully contained in the transitive
reduction $D$ of $D_{h_{1}}$.

Let $h_{2}(e)=q_{0},q_{1},\ldots,q_{\ell}=h_{1}(e)$ be the sequence of
vertices of $Q$ in order. Then by definition of $D_{h_{1}}$, there exist edges
$f_{1},\ldots,f_{\ell}\in\mathcal{E}$ such that $q_{i-1}\in f_{i}$ and
$h_{1}(f_{i})=q_{i}$, for every $i=1,\ldots,\ell$. Suppose first that
$h_{1}(f_{i})=h_{2}(f_{i})$ for every $i=1,\ldots,\ell$. Then
$(q_{i-1},q_{i})\in A(D_{h_{2}})$ for every $i=1,\ldots,\ell$, and clearly we
also have $(h_{1}(e),h_{2}(e))=(q_{\ell},q_{0})\in A(D_{h_{2}})$. This is a
contradiction to $h_{2}$ being an acyclic orientation of $H$. Consequently, at
least one of $f_{1},\ldots,f_{\ell}$ must be contained in
$\mathcal{E}^{\prime}$. Let $j$ be the smallest index such that
$f_{j}\in\mathcal{E}^{\prime}$. We now define $e^{\prime}:=f_{j}$ and
$a=(x,y):=(q_{j-1},q_{j})$. It follows directly from these definitions that
the second item of our claim holds.

Thus, only the third item remains to be verified, which states that $W$,
defined as the prefix of $Q$ up to $x$, together with the arc
$(x,h_{2}(e^{\prime}))$ if $x\not=h_{2}(e^{\prime})$, is a directed path in
$D_{h_{2}}$. To see this, note that by minimality of the choice of $j$, we
have that $h_{2}(f_{i})=h_{1}(f_{i})=q_{i}$ and thus $(q_{i-1},q_{i})\in
A(D_{h_{2}})$ for every $0\leq i\leq j-1$. Furthermore, since $q_{j-1}\in
e^{\prime}=f_{j}$, we have
$(q_{j-1},h_{2}(e^{\prime}))=(q_{j-1},h_{2}(f_{j}))\in A(D_{h_{2}})$ or
$q_{j-1}=h_{2}(e^{\prime})$. Thus the sequence $W$ is a directed walk from
$h_{2}(e)=q_{0}$ to $h_{2}(e^{\prime})$ in $D_{h_{2}}$. It is easy to see that
$W$ is of positive length unless $h_{2}(e)=h_{2}(e^{\prime})$ and $j=1$ (hence
$a$ is the first arc on $Q$). This concludes the proof of the claim. ∎

We next define an infinite sequence $(e_{i})_{i=1}^{\infty}$ of hyperedges
$e_{i}\in\mathcal{E}^{\prime}$ of $H$, as follows. First we pick an element
$e_{1}\in\mathcal{E}^{\prime}$ arbitrarily (note that
$\mathcal{E}^{\prime}\neq\emptyset$ as $h_{1}\neq h_{2}$). Then, for every
$i\geq 1$, having defined $e_{i}$, we define $e_{i+1}\in\mathcal{E}^{\prime}$
as the hyperedge $e^{\prime}$ given by the previous claim, applied with
$e_{i}$ in place of $e$. Concretely, we pick $e_{i+1}$ as an element of
$\mathcal{E}^{\prime}$ such that there exists

  * •

a directed path $Q_{i}$ of length at least two in $D$ from $h_{2}(e_{i})$ to
$h_{1}(e_{i})$,

  * •

an arc $a_{i}=(x_{i},y_{i})$ on $Q_{i}$ such that $x_{i}\in e_{i+1}$ and
$h_{1}(e_{i+1})=y_{i}$,

  * •

and a directed walk $W_{i}$ in $D_{h_{2}}$ from $h_{2}(e_{i})$ to
$h_{2}(e_{i+1})$ which is of length at least $1$, unless
$h_{2}(e_{i})=h_{2}(e_{i+1})$ and $a_{i}$ is the first arc of $Q_{i}$.

###### Claim

There exists $i_{0}\in\mathbb{N}$ such that for every $i\geq i_{0}$ we have
that $h_{2}(e_{i})=h_{2}(e_{i_{0}})$ and $a_{i}$ is the first arc of $Q_{i}$.

###### Proof

Towards a contradiction, suppose there exist infinitely many distinct indices
$i_{1}<i_{2}<i_{3}<\cdots$ such that for every $k\geq 1$, we either have
$h_{2}(e_{i_{k}})\neq h_{2}(e_{i_{k}+1})$ or $a_{i_{k}}$ is not the first arc
on $Q_{i_{k}}$. By the third item above, this means that $W_{i_{k}}$ is of
length at least $1$ for every $k\geq 1$. Since $H$ is finite, there must exist
distinct values $r<s$ such that $h_{2}(e_{i_{r}})=h_{2}(e_{i_{s}})$. But then
the concatenation of the directed walks
$W_{i_{r}},W_{i_{r}+1},\ldots,W_{i_{s}-1}$ forms a closed directed walk in
$D_{h_{2}}$ which is of length at least $1$. This is a contradiction to the
fact that $D_{h_{2}}$ is acyclic, and we thereby conclude the proof of our
claim.∎

In the following, let us denote $v:=h_{2}(e_{i_{0}})$. By the previous claim,
we have that $h_{2}(e_{i})=v$ and $a_{i}=(x_{i},y_{i})$ is the first arc on
$Q_{i}$ for every $i\geq i_{0}$. In particular,
$(h_{2}(e_{i_{0}+1}),h_{1}(e_{i_{0}+1}))=(v,y_{i_{0}})=(x_{i_{0}},y_{i_{0}})=a_{i_{0}}\in
A(Q_{i_{0}})\subseteq A(D)$ is contained in $D$. However, we also have that
$Q_{i_{0}+1}$ is a directed path in $D\subseteq D_{h_{1}}$ starting in
$h_{2}(e_{i_{0}+1})$ and ending in $h_{1}(e_{i_{0}+1})$. Since $Q_{i_{0}+1}$
has length at least two by the first item above, it is a directed path also in
$D_{h_{1}}-(h_{2}(e_{i_{0}+1}),h_{1}(e_{i_{0}+1}))$ parallel to the arc
$(h_{2}(e_{i_{0}+1}),h_{1}(e_{i_{0}+1}))$. This is a contradiction, since by
the above the arc $(h_{2}(e_{i_{0}+1}),h_{1}(e_{i_{0}+1}))$ is contained in
the transitive reduction $D$ of $D_{h_{2}}$. This final contradiction shows
that our initial assumption was incorrect, concluding the proof of the lemma
by the principle of contradiction. ∎

Using Lemma 6, we are now ready to give the proof of Theorem 4.3.

######  Proof (of Theorem 4.3)

We describe an algorithm that takes as input a hypergraph $H=(V,\mathcal{E})$
and two distinct acyclic orientations $h_{1},h_{2}$ of $H$, and returns a flip
sequence $\\{u_{1},v_{1}\\},\ldots,\\{u_{\ell},v_{\ell}\\}$ transforming
$h_{1}$ into $h_{2}$, as follows.

The algorithm starts by going through the list of hyperedges $e$ in
$\mathcal{E}$ and checks whether $h_{1}(e)\neq h_{2}(e)$ and whether the pair
$(h_{1}(e),h_{2}(e))$ is flippable in $h_{1}$. The latter can be done by
checking whether the digraph $D_{h^{e}}$ defined as in the proof of Lemma 6 is
acyclic (which can be done in polynomial time). Once the algorithm has found
an edge $e\in\mathcal{E}$ with $h_{1}(e)\neq h_{2}(e)$ such that
$(h_{1}(e),h_{2}(e))$ is flippable in $h_{1}$ (such an edge $e$ exists by
Lemma 6), it proceeds to define $\\{u_{1},v_{1}\\}:=\\{h_{1}(e),h_{2}(e)\\}$.
If $h^{e}=h_{2}$, then the algorithm returns the flip sequence
$\\{u_{1},v_{1}\\}$ of length $1$ from $h_{1}$ to $h^{e}=h_{2}$. Otherwise, if
$h^{e}\neq h_{2}$, it performs a recursive call on the input pair
$h^{e},h_{2}$ of distinct acyclic orientations, which gives back a flip
sequence
$\\{u_{1}^{\prime},v_{1}^{\prime}\\},\ldots,\\{u_{\ell^{\prime}}^{\prime},v_{\ell^{\prime}}^{\prime}\\}$
from $h^{e}$ to $h_{2}$. The algorithm now returns the concatenated flip
sequence
$\\{u_{1},v_{1}\\},\\{u_{1}^{\prime},v_{1}^{\prime}\\},\ldots,\\{u_{\ell^{\prime}}^{\prime},v_{\ell^{\prime}}^{\prime}\\}$
from $h_{1}$ to $h_{2}$.

Note that with every recursive call of the above algorithm, the number of
hyperedges $f$ for which the two considered orientations of $H$ assign
different heads strictly decreases.

Hence, the above algorithm returns in polynomial time a flip sequence of
length at most $|\\{e\in\mathcal{E}|h_{1}(e)\neq h_{2}(e)\\}|$ from $h_{1}$ to
$h_{2}$.

We next show that

$|\\{e\in\mathcal{E}|h_{1}(e)\neq
h_{2}(e)\\}|\leq\Delta_{2}(H)\cdot\text{dist}(h_{1},h_{2}),$

where $\text{dist}(h_{1},h_{2})$ denotes the length of a shortest flip
sequence transforming $h_{1}$ into $h_{2}$. To see this, note that if we flip
at a pair $\\{u,v\\}$ of vertices in an orientation $h$ of $H$, by definition
of a flip this can only change the value of $h(e)$ for those $e\in E$ with
$\\{u,v\\}\subseteq e$. However, by definition of the codegree there are at
most $\Delta_{2}(H)$ such hyperedges $e$ for every fixed pair $\\{u,v\\}$.
Consequently, in an optimal flip sequence of length $\text{dist}(h_{1},h_{2})$
transforming $h_{1}$ to $h_{2}$, every single flip changes the heads of at
most $\Delta_{2}(H)$ hyperedges, and in total at least
$|\\{e\in\mathcal{E}|h_{1}(e)\neq h_{2}(e)\\}|$ head-assignments have to be
changed. This shows that $|\\{e\in\mathcal{E}|h_{1}(e)\neq
h_{2}(e)\\}|\leq\Delta_{2}(H)\cdot\text{dist}(h_{1},h_{2}),$ as desired. It
follows that the above polynomial-time algorithm indeed returns a
$\Delta_{2}(H)$-approximation of a shortest flip sequence from $h_{1}$ to
$h_{2}$ in $H$. This concludes the proof. ∎

## References

  * [1] Marcelo Aguiar and Federico Ardila.  Hopf monoids and generalized permutahedra.  To appear in Mem. Amer. Math. Soc.; preprint available at https://arxiv.org/abs/1709.07504, 2017.
  * [2] Oswin Aichholzer, Jean Cardinal, Tony Huynh, Kolja Knauer, Torsten Mütze, Raphael Steiner, and Birgit Vogtenhuber.  Flip distances between graph orientations.  Algorithmica, 83(1):116–143, 2021.
  * [3] Oswin Aichholzer, Wolfgang Mulzer, and Alexander Pilz.  Flip distance between triangulations of a simple polygon is NP-complete.  Discrete Comput. Geom., 54(2):368–389, 2015.
  * [4] Federico Ardila, Federico Castillo, Christopher Eur, and Alexander Postnikov.  Coxeter submodular functions and deformations of Coxeter permutahedra.  Adv. Math., 365:107039, 36, 2020.
  * [5] Michel L. Balinski.  On the graph structure of convex polyhedra in $n$-space.  Pacific Journal of Mathematics, 11(2):431–434, 1961.
  * [6] Carolina Benedetti, Nantel Bergeron, and John Machacek.  Hypergraphic polytopes: combinatorial properties and antipode.  J. Comb., 10(3):515–544, 2019.
  * [7] Nicolas Bousquet, Takehiro Ito, Yusuke Kobayashi, Haruka Mizuta, Paul Ouvrard, Akira Suzuki, and Kunihiro Wasa.  Reconfiguration of spanning trees with degree constraints or diameter constraints.  Algorithmica, 85(9):2779–2816, 2023.
  * [8] Jean Cardinal, Hung Phuc Hoang, Arturo I. Merino, Ondrej Micka, and Torsten Mütze.  Combinatorial generation via permutation languages. V. Acyclic orientations.  SIAM J. Discret. Math., 37(3):1509–1547, 2023.
  * [9] Jean Cardinal, Arturo Merino, and Torsten Mütze.  Efficient generation of elimination trees and graph associahedra.  In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2128–2140. [Society for Industrial and Applied Mathematics (SIAM)], Philadelphia, PA, 2022.
  * [10] Jean Cardinal, Lionel Pournin, and Mario Valencia-Pabon.  Diameter estimates for graph associahedra.  Ann. Comb., 26(4):873–902, 2022.
  * [11] Jean Cardinal, Lionel Pournin, and Mario Valencia-Pabon.  The rotation distance of brooms.  European J. Combin., 2023.  To appear.
  * [12] Jean Cardinal, Vera Sacristán, and Rodrigo I. Silveira.  A note on flips in diagonal rectangulations.  Discret. Math. Theor. Comput. Sci., 20(2), 2018.
  * [13] Jean Cardinal and Raphael Steiner.  Inapproximability of shortest paths on perfect matching polytopes.  In Integer Programming and Combinatorial Optimization - 24th International Conference, IPCO 2023, Madison, WI, USA, June 21-23, 2023, Proceedings, volume 13904 of Lecture Notes in Computer Science, pages 72–86. Springer, 2023.
  * [14] Michael P. Carr and Satyan L. Devadoss.  Coxeter complexes and graph-associahedra.  Topology Appl., 153(12):2155–2168, 2006.
  * [15] Cesar Ceballos and Vincent Pilaud.  The diameter of type D associahedra and the non-leaving-face property.  European J. Combin., 51:109–124, 2016.
  * [16] Cesar Ceballos, Francisco Santos, and Günter M. Ziegler.  Many non-equivalent realizations of the associahedron.  Combinatorica, 35(5):513–551, 2015.
  * [17] Sean Cleary and Katherine St. John.  Rotation distance is fixed-parameter tractable.  Inform. Process. Lett., 109(16):918–922, 2009.
  * [18] Jesús A. De Loera, Sean Kafer, and Laura Sanità.  Pivot rules for circuit-augmentation algorithms in linear optimization.  SIAM J. Optim., 32(3):2156–2179, 2022.
  * [19] Harm Derksen and Alex Fink.  Valuative invariants for polymatroids.  Adv. Math., 225(4):1840–1892, 2010.
  * [20] Irit Dinur and Samuel Safra.  On the hardness of approximating minimum vertex cover.  Annals of Mathematics, 162:439–485, 2005.
  * [21] Jack Edmonds.  Submodular functions, matroids, and certain polyhedra.  In Michael Jünger, Gerhard Reinelt, and Giovanni Rinaldi, editors, Combinatorial Optimization — Eureka, You Shrink!: Papers Dedicated to Jack Edmonds 5th International Workshop Aussois, France, March 5–9, 2001 Revised Papers, pages 11–26. Springer Berlin Heidelberg, 2003.
  * [22] Satoru Fujishige.  Submodular functions and optimization, volume 58 of Annals of Discrete Mathematics.  Elsevier B. V., Amsterdam, second edition, 2005.
  * [23] Komei Fukuda, Alain Prodon, and Tadashi Sakuma.  Notes on acyclic orientations and the shelling lemma.  Theoretical Computer Science, 263(1–2):9–16, 2001.
  * [24] Israel M. Gelfand, R. Mark Goresky, Robert D. MacPherson, and Vera V. Serganova.  Combinatorial geometries, convex polyhedra, and Schubert cells.  Adv. in Math., 63(3):301–316, 1987.
  * [25] Tatsuya Gima, Takehiro Ito, Yasuaki Kobayashi, and Yota Otachi.  Algorithmic meta-theorems for combinatorial reconfiguration revisited.  In Shiri Chechik, Gonzalo Navarro, Eva Rotenberg, and Grzegorz Herman, editors, 30th Annual European Symposium on Algorithms, ESA 2022, September 5-9, 2022, Berlin/Potsdam, Germany, volume 244 of LIPIcs, pages 61:1–61:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.
  * [26] Curtis Greene.  Acyclic orientations.  In Proceedings of the NATO Advanced Study Institute held in Berlin (West Germany), September 1-10, 1976, 1977.
  * [27] Curtis Greene and Thomas Zaslavsky.  On the interpretation of Whitney numbers through arrangements of hyperplanes, zonotopes, non-Radon partitions, and orientations of graphs.  Trans. Amer. Math. Soc., 280(1):97–126, 1983.
  * [28] Johan Håstad.  Some optimal inapproximability results.  Journal of the ACM, 48(4):798–859, 2001.
  * [29] Thorkell Helgason.  Aspects of the theory of hypermatroids.  In Claude Berge and Dijen Ray-Chaudhuri, editors, Hypergraph Seminar, pages 191–213. Springer Berlin Heidelberg, 1974.
  * [30] Jan van den Heuvel.  The complexity of change, pages 127–160.  London Mathematical Society Lecture Note Series. Cambridge University Press, 2013.
  * [31] Warren M. Hirsch and George B. Dantzig.  The fixed charge problem.  Naval Research Logistics Quarterly, 15(3):413–424, 1968.
  * [32] Tim H. Hultberg and Domingos M. Cardoso.  The teacher assignment problem: A special case of the fixed charge transportation problem.  Eur. J. Oper. Res., 101(3):463–473, 1997.
  * [33] Takehiro Ito, Erik D. Demaine, Nicholas J. A. Harvey, Christos H. Papadimitriou, Martha Sideri, Ryuhei Uehara, and Yushi Uno.  On the complexity of reconfiguration problems.  Theor. Comput. Sci., 412(12-14):1054–1065, 2011.
  * [34] Takehiro Ito, Yuni Iwamasa, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Shun-ichi Maezawa, Yuta Nozaki, Yoshio Okamoto, and Kenta Ozeki.  Monotone edge flips to an orientation of maximum edge-connectivity à la Nash-Williams.  ACM Trans. Algorithms, 19(1):6:1–6:22, 2023.
  * [35] Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Shun-ichi Maezawa, Yuta Nozaki, and Yoshio Okamoto.  Hardness of finding combinatorial shortest paths on graph associahedra.  In Kousha Etessami, Uriel Feige, and Gabriele Puppis, editors, 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023, July 10-14, 2023, Paderborn, Germany, volume 261 of LIPIcs, pages 82:1–82:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.
  * [36] Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, and Yoshio Okamoto.  Shortest reconfiguration of perfect matchings via alternating cycles.  SIAM J. Discret. Math., 36(2):1102–1123, 2022.
  * [37] Takehiro Ito, Marcin Jakub Kaminski, Hirotaka Ono, Akira Suzuki, Ryuhei Uehara, and Katsuhisa Yamanaka.  Parameterized complexity of independent set reconfiguration problems.  Discret. Appl. Math., 283:336–345, 2020.
  * [38] Takehiro Ito, Hirotaka Ono, and Yota Otachi.  Reconfiguration of cliques in a graph.  Discret. Appl. Math., 333:43–58, 2023.
  * [39] Iyad Kanj, Eric Sedgwick, and Ge Xia.  Computing the flip distance between triangulations.  Discrete Comput. Geom., 58(2):313–344, 2017.
  * [40] Shirley Law and Nathan Reading.  The Hopf algebra of diagonal rectangulations.  J. Combin. Theory Ser. A, 119(3):788–824, 2012.
  * [41] Haohong Li and Ge Xia.  An O(3.82${}^{\mbox{k}}$) time FPT algorithm for convex flip distance.  In Petra Berenbrink, Patricia Bouyer, Anuj Dawar, and Mamadou Moustapha Kanté, editors, 40th International Symposium on Theoretical Aspects of Computer Science, STACS 2023, March 7-9, 2023, Hamburg, Germany, volume 254 of LIPIcs, pages 44:1–44:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.
  * [42] Jean-Louis Loday.  Realization of the Stasheff polytope.  Arch. Math. (Basel), 83(3):267–278, 2004.
  * [43] Anna Lubiw and Vinayak Pathak.  Flip distance between two triangulations of a point set is NP-complete.  Comput. Geom., 49:17–23, 2015.
  * [44] Thibault Manneville and Vincent Pilaud.  Graph properties of graph associahedra.  Sém. Lothar. Combin., 73:Art. B73d, 31, [2014–2016].
  * [45] Emily Meehan.  The Hopf algebra of generic rectangulations.  arXiv:1903.09874, 2019.
  * [46] Arturo I. Merino and Torsten Mütze.  Combinatorial generation via permutation languages. III. rectangulations.  Discret. Comput. Geom., 70(1):51–122, 2023.
  * [47] Christina M. Mynhardt and Shahla Nasserasr.  50 years of Combinatorics, Graph Theory, and Computing: Reconfiguration of Colourings and Dominating Sets in Graphs, chapter 10.  Chapman and Hall, 2019.
  * [48] Arnau Padrol, Vincent Pilaud, and Julian Ritter.  Shard polytopes.  Sém. Lothar. Combin., 85B:Art. 11, 12, 2021.
  * [49] Vincent Pilaud.  Acyclic reorientation lattices and their lattice quotients.  Proceedings of the 34th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC), 2022.
  * [50] Vincent Pilaud and Francisco Santos.  Quotientopes.  Bull. Lond. Math. Soc., 51(3):406–420, 2019.
  * [51] Vincent Pilaud, Francisco Santos, and Günter M. Ziegler.  Celebrating Loday’s associahedron.  Arch. Math. (Basel), 2023.  To appear.
  * [52] Alex Postnikov, Victor Reiner, and Lauren Williams.  Faces of generalized permutohedra.  Doc. Math., 13:207–273, 2008.
  * [53] Alexander Postnikov.  Permutohedra, associahedra, and beyond.  Int. Math. Res. Not. IMRN, 2009(6):1026–1106, 2009.
  * [54] Lionel Pournin.  The diameter of associahedra.  Adv. Math., 259:13–42, 2014.
  * [55] Nathan Reading.  Generic rectangulations.  European J. Combin., 33(4):610–623, 2012.
  * [56] Sophie Rehberg.  Pruned inside-out polytopes, combinatorial reciprocity theorems and generalized permutahedra.  Electron. J. Comb., 29(4), 2022.
  * [57] Susann Schrenk, Gerd Finke, and Van-Dat Cung.  Two classical transportation problems revisited: pure constant fixed charges and the paradox.  Math. Comput. Modelling, 54(9-10):2306–2315, 2011.
  * [58] Alexander Schrijver.  Combinatorial Optimization - Polyhedra and Efficiency, volume 24 of Algorithms and Combinatorics.  Springer, 2003.
  * [59] Daniel D. Sleator, Robert E. Tarjan, and William P. Thurston.  Rotation distance, triangulations, and hyperbolic geometry.  J. Amer. Math. Soc., 1(3):647–681, 1988.
  * [60] Richard P. Stanley.  Acyclic orientations of graphs.  Discrete Math., 5:171–178, 1973.
  * [61] Dirk Vertigan and Geoff Whittle.  Recognizing polymatroids associated with hypergraphs.  Combinatorics, Probability and Computing, 2(4):519–530, 1993.


Advance Access Publication Date: 20 Nov 2021 Letter

∗To whom correspondence should be addressed.

Received on X; revised on X; accepted on X

Associate Editor: X

# Continuous-time Markov chain as a generic trait-based evolutionary model

Genome Analysis

Ali Amiryousefi ${}^{\text{\sfb 1}*}$ ${}^{\text{\sf 1}}$Systems Oncology
Unit, Faculty of Medicine, University of Helsinki, Helsinki, Finland.

(2015; 2015)

###### Abstract

More than ever, today we are left with the abundance of molecular data
outpaced by the advancements of the phylogenomic methods. Especially in the
case of presence of many genes over a set of species under the phylogeny
question, more sophisticated methods than the crude way of concatenation is
needed. In this letter, by placing the continuous-time Markov chain (CTMC) on
the species set, I present a novel model for inferring the phylogeny,
obtaining the network graph, or drawing the proximity conclusions. The rate of
transition between states is calculated based on the binary character paths
between each two species. This is the base for the pairwise distances between
species. Next to its generic use, the formulation of the model allows the
site-wise phylogenetic inference and a mathematically justified method of
combining these information to form as big as the whole genome phylogenetic
inference. Although based on the characters or traits, this model is
inherently a distance method but its advantage to other methods of the same
class is its ability to incorporate the information of all the other species
in forming the pairwise distance between two them. Contact:
ali.amiryousefi<EMAIL_ADDRESS>Key words: Continuous-
time Markov chain, neighbouring-box process, evolutionary model

## BACKGROUND

Given a set of species, there are many methods to call for their phylogenetic
tree based on their specific characteristics. In specific, in the molecular
evolution context, the richness of the methods both in the quantity and
quality is significant. This richness should not indicate the fallacy of the
exactness of the models since each model makes its own simplifications and
assumptions with regard to the evolutionary mechanism. For example, the
distance based methods base their distances on nucleotide evolutionary model
that often controversy arise for the choice of an appropriate one. The
character based methods, besides this dilemma, carry on the burden of the
sites independence and furthermore, likelihood based models suffers from an
expensive computational efficiency in finding the right tree. Molecular clock
is another assumption that most of the models explicitly make. On the other
hand, different models, use the available data with a different degree of
efficiency. The parsimony based methods for example, will not use the sites
with at most one different characters and distance based methods will neglect
the sites with gaps in their analysis. Nonetheless, these models were able to
give us reasonably good phylogenies with some statistical properties that made
them readily more interesting choices to form the phylogenetic tree when the
molecular data is available (Wheeler, 2012; Felsenstein, 2004).

Here with placing the CTMC over the species set rather than character set, I
introduce a novel point of view toward evolution of a molecular sequences.
This minimal modification to the distance methods, will leave us with a
significant rewards in delineating the genealogical relationship of a given
set of species. The rate of transition between states of the chain will be
calculated based on the frequency of the character paths between each two
states. The embedded transition matrix will then be calculated for each site
and the multiplication of these matrices over all sites will be the final
transition matrix that is viewed as the species distances. The advantage of
this model is its ability to sum over all the other observed characters of
species when forming the distance between two species. This is dramatically
different from the basic distance methods that after adhering to a specific
evolutionary model, will calculate the pairwise distance of two sequences
irrespective of the other species distances. As long as the goal of any
phylogenetic method is to decipher the historical dependency of the species,
this implicit ignorance, implying the independence of species is abominable.
The representation of the model enables a mathematically justified method of
combining different evolutionary information among the species and a
computationally tractable solution of the phylogenetic tree in the presence of
massive data. The former property is specially attractive when interested in
the species tree with the availability of more than one gene tree or alignment
while latter is appealing in the existence of the genomic size data over
species set. The other advantage of this formulation is its ability to
integrate the sites with gaps and its mixing ability that allows elucidation
of a single phylogenetic tree in the existence of different types of
independent evolutionary characters throughout species.

## NEIGHBORING BOX PROCESS

Here I define the neighbouring box process (NBP), as the generative model of
the generic trait evolution. Consider the evolution of an artificial species
in a box with only one trait. This trait can be a letter from any closed
alphabet set. Furthermore consider this trait to be governed by an evolution
machinery under an assumed molecular clock. This indicates the passage of
exponentially distributed amount of time before any substitution or deletion
takes place. The emergence of a new species through this species therefore can
be considered as an exponential distribution too, albeit with different
parameters. Now lets assume that the box is embedded with a speciation and
extinction switches. Anytime the species in the box hits the speciation
switch, a new artificial species will be formed in a neighboring brand new box
and start its evolutionary life like its anscestor species. On the other hand,
each time the species hits the extinction switch, the box in which it is
living, will be vanished into abyss111The case of insertion can be considered
as the incidence of new trait that can be put in a new box ruled by the same
molecular mechanism. The state of the species at anytime is the letter
observed for that trait. This is a process that is assumed to be followed
along the time from past till now and we are given a number of boxes with
their corresponding observed letters of a trait. From the time of emergence of
a species the fate of the evolution under this process can be depicted. Only
one of the realization of this process has happened in the past time leaving
us with the diversity of species around us and the goal of each evolutionary
model is to estimate this specific line of history as closely as possible. In
the following section I introduce one of such models based on the CTMC which
imitates the latter process assumptions.

## THE MODEL FORMULATION

Assume that a neighboring box process with an initial species is started at
some point in the past given rise to number of species at this time. For a
specific trait, each species is registered with a letter and this is all the
information that we have about the evolution history of the set of species in
hand. We can assume that all the species in each box can communicate with each
other with a given rate. This is like assuming that the species are the states
of an ergodic CTMC which are communicating through the two way paths
represented by the letters of two states. Consider the vector
$\textbf{v}=(v_{1},v_{2},\ldots,v_{n})$ as the site characters of a given
alignment for $n$ species $\textbf{s}=(s_{1},s_{2},\ldots,s_{n})$. These
characters can be a letter of any known closed alphabet set. In specific,
these sets can be any of $\mathcal{N}=\\{A,C,G,T\\}$,
$\mathcal{A}=\\{His,Asp,\ldots,Val\\}$,
$\mathcal{C}=\\{UUU,UUC,\ldots,GGG\\}$, or $\mathcal{M}=\\{1,2,\ldots\\}$ as
nucleotide, amino acid residues, codons, or morphological attributes,
respectively.
Given this vector, we define the path matrix of
$\textbf{V}=\textbf{v}\otimes\textbf{v}.$ This is the matrix which shows all
the possible alphabetic paths from each species to another.

$V_{n,n}=\mathbf{v}\mathbf{v}^{T}=\begin{pmatrix}v_{1}v_{1}&v_{1}v_{2}&\cdots&v_{1}v_{n}\\\
v_{2}v_{1}&v_{2}v_{2}&\cdots&a_{2}v_{n}\\\ \vdots&\vdots&\ddots&\vdots\\\
v_{n}v_{1}&v_{n}v_{2}&\cdots&v_{n}v_{n}\end{pmatrix}.$ (1)

Now each element of this matrix shows an alphabetic path through which two
species communicate. These communications can form a saturated network of
species. The species can be considered as the states of a CTMC and we can use
the frequency proportion of the paths in the network as the transition rate
between species. With defining $f_{v_{.}}$ as the frequency of $v_{.}$ letter
in the site, one can obtain the transition rate matrix $Q_{n,n}$ based on the
collection of all these values as follow,

$Q_{n,n}=(q_{ij})=\begin{cases}\frac{f_{v_{i}}f_{v_{j}}}{n(n-1)}&\quad\text{if
}i\neq j,v_{i}\neq v_{j}\\\
\frac{f_{v_{i}}(f_{v_{i}}-1)}{n(n-1)}&\quad\text{if }i\neq j,v_{i}=v_{j}\\\
-\sum_{i\neq j}q_{ij}&\quad\text{if }i=j\\\ \end{cases}.$ (2)

Upon obtaining the transition rate matrix $Q$, we can derive the embedded
stochastic transition matrix $P$ as,

$P_{n,n}=(p_{ij})=\begin{cases}\frac{q_{ij}}{\sum_{i\neq
j}q_{ij}}&\quad\text{if }i\neq j\\\ 1-\sum_{i\neq j}p_{ij}&\quad\text{if
}i=j\\\ \end{cases}.$ (3)

Ideally, we are more interested on the transition matrix $P_{t}$ so that we
can answer more queries with respect of time variable in Markov process. On
the other hand, the calculation of this matrix is computationally expensive
and even intractable in the cases of many species. This factor, beside the
long enough time in history to permit for the set of species to emerge,
renders the use of infinite time value an interesting choice222Note that if
one could derive the $P_{t}$ then setting the $t$ as the entropy of
$\mathbf{v}$ would be a reasonable choice so that the least conserved sites
have the most time to be emerged. This choice of $t$ is quite natural since if
there is higher entropy in the site this represents a larger scale of time for
the evolution of the neighboring box process. Upon this imputation of time
variable in transition matrix, we will be left with a stochastic matrix $P$..
Since this matrix is denoting an ergodic Markov chain. Furthermore, through
the formulation of $Q$, it follows that the Markov chain is reversible. For
example a simple scenario of 4 species with $\mathbf{v}=(x,x,y,z)$ is leading
to the following network graph of this site as well as the binary path matrix
$V_{4,4}$;

$s_{1}$$s_{2}$$s_{3}$$s_{4}$$v_{1}v_{1}$$v_{1}v_{2}$$v_{2}v_{2}$$v_{3}v_{3}$$v_{3}v_{1}$$v_{4}v_{4}$$v_{4}v_{2}$$v_{4}v_{3}$
(4)

$V_{4,4}=\begin{pmatrix}xx&xx&xy&xz\\\ xx&xx&xy&xz\\\ yx&yx&yy&yz\\\
zx&zx&zy&zz\end{pmatrix}.$ (5)

## CONCLUSION

While relaxing the choice of evolutionary model, the neighboring box process
is still preserving the site independence and molecular clock assumption often
tied with other evolutionary models. Furthermore, considering the infinite
time for the evolution and since $P^{(t)}=e^{Qt}$, we have $P^{(\infty)}=P$.
Gathering all these matrices for each species in our set, we can form the
distance matrix $D=\frac{1}{P_{1}\times P_{2}\times\ldots P_{n}}$ as the basis
of tree or network derivation of the given set of species.

## References

  * Felsenstein (2004) Felsenstein (2004).  Inferring phylogenies, volume 2.  Sinauer associates Sunderland, MA.
  * Wheeler (2012) Wheeler, W. C. (2012).  Systematics: a course of lectures.  John Wiley & Sons.