Graduate School of Information Sciences, Tohoku University,
Japantakehiro@tohoku.ac.jphttps://orcid.org/0000-0002-9912-6898JSPS KAKENHI
Grant Numbers JP18H04091, JP19K11814, JP20H05793 Faculty of Science and
Technology, Keio University,
Japankakimura@math.keio.ac.jphttps://orcid.org/0000-0002-3918-3479JSPS KAKENHI
Grant Numbers JP20H05795, JP21H03397, JP22H05001 Institute of Mathematics for
Industry, Kyushu University,
Japankamiyama@imi.kyushu-u.ac.jphttps://orcid.org/0000-0002-7712-2730JSPS
KAKENHI Grant Number JP20H05795 Research Institute for Mathematical Sciences,
Kyoto University,
Japanyusuke@kurims.kyoto-u.ac.jphttps://orcid.org/0000-0001-9478-7307JSPS
KAKENHI Grant Numbers JP20K11692, JP20H05795, JP22H05001 Department of
Mathematics, Tokyo University of Science,
Japanmaezawa.mw@gmail.comhttps://orcid.org/0000-0003-1607-8665JSPS KAKENHI
Grant Numbers JP20H05795, JP22K13956 Faculty of Environment and Information
Sciences, Yokohama National University, Japan and SKCM2, Hiroshima University,
Japannozaki-yuta-vn@ynu.ac.jphttps://orcid.org/0000-0003-3223-0153JSPS KAKENHI
Grant Numbers JP20H05795, JP20K14317, JP23K12974 Graduate School of
Informatics and Engineering, The University of Electro-Communications,
Japanokamotoy@uec.ac.jphttps://orcid.org/0000-0002-9826-7074JSPS KAKENHI Grant
Numbers JP20H05795, JP20K11670, JP23K10982 Takehiro Ito, Naonori Kakimura,
Naoyuki Kamiyama, Yusuke Kobayashi, Shun-ichi Maezawa, Yuta Nozaki, and Yoshio
Okamoto [500]Mathematics of computing Combinatorics [500]Theory of computation
Problems, reductions and completeness

###### Acknowledgements.

This work was motivated by the talks of Vincent Pilaud and Jean Cardinal at
Workshop “Polytope Diameter and Related Topics,” held online on September 2,
2022. We thank them for inspiration. We are also grateful to Yuni Iwamasa and
Kenta Ozeki for the discussion and to the anonymous reviewers for their
helpful comments.

# Hardness of Finding Combinatorial Shortest Paths on Graph Associahedra

Takehiro Ito  Naonori Kakimura  Naoyuki Kamiyama  Yusuke Kobayashi  Shun-ichi
Maezawa  Yuta Nozaki  Yoshio Okamoto

###### Abstract

We prove that the computation of a combinatorial shortest path between two
vertices of a graph associahedron, introduced by Carr and Devadoss, is NP-
hard. This resolves an open problem raised by Cardinal. A graph associahedron
is a generalization of the well-known associahedron. The associahedron is
obtained as the graph associahedron of a path. It is a tantalizing and
important open problem in theoretical computer science whether the computation
of a combinatorial shortest path between two vertices of the associahedron can
be done in polynomial time, which is identical to the computation of the flip
distance between two triangulations of a convex polygon, and the rotation
distance between two rooted binary trees. Our result shows that a certain
generalized approach to tackling this open problem is not promising. As a
corollary of our theorem, we prove that the computation of a combinatorial
shortest path between two vertices of a polymatroid base polytope cannot be
done in polynomial time unless $\mathrm{P}=\mathrm{NP}$. Since a combinatorial
shortest path on the matroid base polytope can be computed in polynomial time,
our result reveals an unexpected contrast between matroids and polymatroids.

###### keywords:

Graph associahedra, combinatorial shortest path, NP-hardness, polymatroids

###### category:

##  1 Introduction

Graph associahedra were introduced by Carr and Devadoss [8]. These polytopes
generalize associahedra. In an associahedron, each vertex corresponds to a
binary tree over a set of $n$ elements, and each edge corresponds to a
rotation operation between two binary trees. For the historical account of
associahedra, see the introduction of the paper by Ceballos, Santos, and
Ziegler [9].

A binary tree can be obtained from a labeled path. Let $V=\\{1,2,\dots,n\\}$
be the set of vertices of the path, and $E=\\{\\{i,i+1\\}\mid 1\leq i\leq
n-1\\}$ be the set of edges of the path. To construct a labeled binary tree,
we choose an arbitrary vertex from the path. Let it be $i\in V$. Then, the
removal of $i$ from the path results in at most two connected components: the
left subpath and the right subpath, which may be empty. Then, in the
corresponding binary tree, we set $i$ as a root, and append recursively a
binary tree of the left subpath as a left subtree and a binary tree of the
right subpath as a right subtree. Note that in this construction, each node of
the binary tree is labeled by a vertex of the path.

In the construction of graph associahedra, we follow the same idea. Since we
are only interested in the graph structure of graph associahedra in this work,
we only describe their vertices and edges. To define a graph associahedron, we
first fix a connected undirected graph $G=(V,E)$.111A graph associahedron can
also be defined for disconnected graphs, but in this paper, we concentrate on
connected graphs. Then, in the $G$-associahedron, the vertices correspond to
the so-called elimination trees of $G$, and the edges correspond to swap
operations between two elimination trees. The following description follows
that of Cardinal, Merino, and Mütze [5].

An _elimination tree_ of a connected undirected graph $G=(V,E)$ is a rooted
tree defined as follows. It has $V$ as the vertex set and is composed of a
root $v\in V$ that has as children elimination trees for each connected
component of $G-v$ (Figure 1). A swap from an elimination tree $T$ to another
elimination tree $T^{\prime}$ of $G$ is defined as follows. Let $v$ be a non-
root vertex of $T$, and let $u$ be the parent of $v$ in $T$. Denote by $H$ the
subgraph of $G$ induced by the subtree rooted at $v$ in $T$. Then, the swap of
$u$ with $v$ transforms $T$ to $T^{\prime}$ as follows. (1) The tree
$T^{\prime}$ has $v$ as the parent of $u$, and $T^{\prime}$ has $v$ as a child
of the parent of $u$ in $T$. (2) The subtrees rooted at $u$ in $T$ remain
subtrees rooted at $u$ in $T^{\prime}$. (3) A subtree $S$ rooted at $v$ in $T$
remains a subtree rooted at $v$ in $T^{\prime}$, unless the vertices of $S$
belong to the same connected component of $H-v$ as $u$, in which case $S$
becomes a subtree rooted at $u$ in $T^{\prime}$. The $G$-associahedron for a
claw $G$ is given in Figure 2. Note that a swap operation is reversible.

Figure 1: An example of elimination trees. Two trees $T$ and $T^{\prime}$ are
elimination trees of the graph $G$. The tree $T^{\prime}$ is obtained from $T$
by the swap of $i$ with $j$. The example is borrowed from Cardinal, Merino,
and Mütze [5]. Figure 2: An example of a graph associahedron. Each vertex of
the polytope corresponds to an elimination tree of the graph $G$.

In this paper, among graph properties of graph associahedra, we concentrate on
the computation of a combinatorial shortest path (i.e., the graph-theoretic
distance) between two vertices of the polytope, which we call the
combinatorial shortest path problem on graph associahedra. In this problem, we
are given a graph $G$ and two elimination trees $T,T^{\prime}$ of $G$, and
want to compute the shortest length of a graph-theoretic path from $T$ to
$T^{\prime}$ on the $G$-associahedron. In the literature, we only find the
studies in the case where $G$ is a complete graph or (a generalization of) a
star. When $G$ is a complete graph, the $G$-associahedron is called a
permutahedron, and each of its vertices corresponds to a permutation. Since an
edge corresponds to an adjacent transposition, the graph-theoretic distance
between two vertices is equal to the number of inversions between the
corresponding permutations. This can be computed in polynomial time. When $G$
is a star, the $G$-associahedron is called stellohedron [27]. Recently,
Cardinal, Pournin, and Valencia-Pabon [7] gave a polynomial-time algorithm to
compute a combinatorial shortest path on stellohedra, and they generalize the
algorithm when $G$ is a complete split graph (i.e., a graph obtained from a
star by replacing the center vertex with a clique).

On the other hand, it is a tantalizing open problem whether a combinatorial
shortest path can be computed in polynomial time when $G$ is a path. In this
case, the graph-theoretic distance corresponds to the rotation distance
between two binary trees. By Catalan correspondences, this is equivalent to
the flip distance between two triangulations of a convex polygon. A possible
strategy to resolve this open problem is to generalize the problem and solve
the generalized problem. In our case, a generalization is achieved by
considering graph associahedra for general graphs.

Our main result states that the combinatorial shortest path problem on
$G$-associahedra is $\mathrm{NP}$-hard when $G$ is also given as part of the
input. This implies that the strategy mentioned above is bound to fail.

First, we formally state the problem Combinatorial Shortest Path on Graph
Associahedra as follows.

Combinatorial Shortest Path on Graph Associahedra
---
Input: A graph $G$ and two elimination trees
$T_{\mathrm{ini}},T_{\mathrm{tar}}$ of $G$
Output: The distance between $T_{\mathrm{ini}}$ and $T_{\mathrm{tar}}$ on the
graph of the $G$-associahedron

Our first theorem states the $\mathrm{NP}$-hardness of Combinatorial Shortest
Path on Graph Associahedra. This solves an open problem raised by Cardinal
(see [3, Section 4.2]).

######  Theorem 1.1.

Combinatorial Shortest Path on Graph Associahedra is $\mathrm{NP}$-hard.

Theorem 1.1 yields the following corollary, which is related to polymatroids
introduced by Edmonds [13]. A pair $(U,\rho)$ of a finite set $U$ and a
function $\rho\colon 2^{U}\to\mathbb{R}$ is called a _polymatroid_ if $\rho$
satisfies the following conditions: (P1) $\rho(\emptyset)=0$; (P2) if
$X\subseteq Y\subseteq U$, then $\rho(X)\leq\rho(Y)$; (P3) if $X,Y\subseteq
U$, then $\rho(X\cup Y)+\rho(X\cap Y)\leq\rho(X)+\rho(Y)$. The function $\rho$
is called the _rank function_ of the polymatroid $(U,\rho)$.

For a polymatroid $(U,\rho)$, we define the _base polytope_ of $(U,\rho)$ as

$\mathbf{B}(\rho):=\\{x\in\mathbb{R}^{U}\mid
x(X)\leq\rho(X)\,(\forall\,X\subseteq U),\,x(U)=\rho(U)\\},$

where we define $x(X):=\sum_{u\in X}x(u)$ for each subset $X\subseteq U$.
Then, $\mathbf{B}(\rho)$ is a polytope because
$0\leq\rho(U)-\rho(U\setminus\\{u\\})=x(U)-\rho(U\setminus\\{u\\})\leq
x(u)\leq\rho(\\{u\\})$ for every element $e\in E$.

A polymatroid is seen as a polyhedral generalization of a matroid. For
example, the greedy algorithm for matroids can be treated as an algorithm to
maximize a linear function over the base polytope of a matroid,222This can
further be seen as a generalization of Kruskal’s algorithm for the minimum
spanning tree problem. and the algorithm is readily generalized to the base
polytope of a polymatroid. A lot of combinatorial properties of the base
polytopes of matroids also hold for the base polytopes of polymatroids. Since
it is known that a combinatorial shortest path on the base polytope of a
matroid can be computed in polynomial time [18], we are interested in
generalizing this result to polymatroids, which leads to the following problem
definition.

Combinatorial Shortest Path on Polymatroids
---
Input: An oracle access to a polymatroid $(U,\rho)$ and two extreme points
$x_{\mathrm{ini}},x_{\mathrm{tar}}$ of the base polytope $\mathbf{B}(\rho)$
Output: The distance between $x_{\mathrm{ini}}$ and $x_{\mathrm{tar}}$ on
$\mathbf{B}(\rho)$

We note that a polymatroid $(U,\rho)$ is given as an oracle access that
returns the value $\rho(X)$ for any set $X\subseteq U$. The running time of an
algorithm is also measured in terms of the number of oracle calls. This is a
standard assumption when we deal with polymatroids [16] since if we would
input the function $\rho$ as a table of the values $\rho(X)$ for all
$X\subseteq U$, then it would already take at least $2^{|U|}$ space. We also
note that the adjacency of two extreme points of the base polytope of a
polymatroid can be tested in polynomial time [33].

The next theorem states that this problem is hard, which is proved as a
corollary of Theorem 1.1, and reveals an unexpected contrast between matroids
and polymatroids.

######  Theorem 1.2.

There exists no polynomial-time algorithm for Combinatorial Shortest Path on
Polymatroid unless $\mathrm{P}=\mathrm{NP}$.

Our proof relies on the fact that graph associahedra can be realized as the
base polytopes of some polymatroids [27]. However, we need careful treatment
since in the reduction we require the rank function of our polymatroid to be
evaluated in polynomial time. To this end, we give an explicit inequality
description of the realization of a graph associahedron due to Devadoss
[12],333We note here that the original definition of a graph associahedron by
Carr and Devadoss [8] does not give explicit vertex coordinates of the
polytope. Therefore, we rely on the realization by Devadoss [12] who gave the
explicit vertex coordinates.  which is indeed the base polytope of a
polymatroid.

### Related Work

Paths on polytopes have been studied thoroughly. One of the initial
motivations for this research direction is to design and understand path-
following algorithms for linear optimization such as simplex methods. In his
chapter of Handbook of Discrete and Computational Geometry [17], Kalai stated
as an open problem “Find an efficient routing algorithm for convex polytopes.”
Here, a routing algorithm means one that finds a short path from a given
initial vertex to a given target vertex.

Paths on graph associahedra have been receiving much attention. The diameter
is perhaps the most frequently studied quantity, which is defined as the
maximum distance between two vertices of the polytope. A famous result by
Sleator, Tarjan, and Thurston [32] states that the diameter of the
$(n-1)$-dimensional associahedron (i.e., a graph associahedron of an
$n$-vertex path) is at most $2n-6$ when $n\geq 11$ and this bound is tight for
all sufficiently large $n$. This bound is refined by Pournin [28], who proved
that the diameter of the $(n-1)$-dimensional associahedron is exactly $2n-6$
when $n\geq 11$.

For a general $n$-vertex graph $G$, Manneville and Pilaud [25] proved that the
diameter of $G$-associahedron is at most $\binom{n}{2}$ and at least
$\max\\{m,2n-20\\}$, when $m$ is the number of edges of $G$. The upper bound
is attained by the case where $G$ is a complete graph (i.e., the
$G$-associahedron is a permutahedron). When $G$ is an $n$-vertex star (i.e.,
$K_{1,n-1}$), $n\geq 6$, Manneville and Pilaud [25] showed that the diameter
is $2n-2$. When $G$ is a cycle (i.e., the polytope is a cyclohedron), Pournin
[29] gave the asymptotically exact diameter. When $G$ is a tree, Manneville
and Pilaud [25] gave the upper bound $O(n\log n)$ while Cardinal, Langerman,
and Pérez-Lantero [4] gave an example of trees for which the diameter is
$\Omega(n\log n)$ (such an example is chosen as a complete binary tree).
Cardinal, Pournin, and Valencia-Pabon [6] proved that the diameter is
$\Theta(m)$ for $m$-edge trivially perfect graphs, and gave upper and lower
bounds for the diameter in terms of treewidths, pathwidths, and treedepths of
graphs. Berendsohn [2] proved that the diameter is $\Theta(n+mH)$ for a
caterpillar with $n$ spine vertices, $m$ leg vertices, and the Shannon entropy
$H$ of the so-called leg distribution.

To the authors’ knowledge, the complexity of computing the diameter of graph
associahedra has not been investigated. When polytopes are not restricted to
graph associahedra, a few hardness results have been known. Frieze and Teng
[15] proved that computing the diameter of a polytope, given by inequalities,
is weakly NP-hard. Sanità [30] proved that computing the diameter of the
fractional matching polytope of a given graph is strongly NP-hard. Kaibel and
Pfetsch [19] raised an open problem about the complexity of computing the
diameter of simple polytopes.

The computation of a combinatorial shortest path on a $G$-associahedron has
also been studied. It is a long-standing open problem whether a combinatorial
shortest path in an associahedron (i.e., a $G$-associahedron when $G$ is a
path) can be computed in polynomial time. Polynomial-time algorithms are only
known when $G$ is a complete graph (folklore), a star, or a complete split
graph (Cardinal, Pournin, and Valencia-Pabon [7]). When $G$ is a path, a
polynomial-time approximation algorithm of factor two [11] and fixed-parameter
algorithms when the distance is a parameter [10, 20, 21, 24] are known.

Since a combinatorial shortest path on an associahedron is equivalent to a
shortest flip sequence of triangulations of a convex polygon, the computation
of a shortest flip sequence of triangulations has been studied in more general
setups. For triangulations of point sets, the problem is $\mathrm{NP}$-hard
[23] and even $\mathrm{APX}$-hard [26]. For triangulations of simple polygons,
the problem is also $\mathrm{NP}$-hard [1].

Elimination trees have appeared in a lot of branches of mathematics and
computer science. For a good summary, see Cardinal, Merino, and Mütze [5].

### Technique Overview

To prove the hardness of the combinatorial shortest path problem on graph
associahedra, we first consider a “weighted” version of the combinatorial
shortest path problem on graph associahedra, which is newly introduced in this
paper for our reduction. In this problem, each vertex of a given graph has a
positive weight, and the swap of two vertices incurs the weight that is
defined as the product of the weights of these two vertices. The weight of a
swap sequence is defined as the sum of weights of swaps in the sequence. As
our intermediate theorem, we prove that this weighted version is strongly
$\mathrm{NP}$-hard.

To this end, we reduce the $\mathrm{NP}$-hard problem of finding a balanced
minimum $s$-$t$ cut in a graph [14] to the weighted version of the
combinatorial shortest path problem on graph associahedra. In the balanced
minimum $s$-$t$ cut problem, we want to determine whether there exists a
minimum $s$-$t$ cut of a given graph $G$ that is a bisection of the vertex
set. In the reduction, we construct a vertex-weighted graph $H$ from $G$ and
two elimination trees $T_{\mathrm{ini}}$, $T_{\mathrm{tar}}$ of $H$. The
weighted graph $H$ is constructed by replacing $s$ and $t$ by large cliques,
subdividing each edge, and duplicating each vertex; the weights are assigned
so that the subdivision vertices receive small weights, and duplicated
vertices and vertices in large cliques receive large weights. Elimination
trees $T_{\mathrm{ini}}$ and $T_{\mathrm{tar}}$ are constructed so that
swapping two vertices of large weights is forbidden and identifying a few
vertices of small weights (that corresponds to a balanced minimum $s$-$t$ cut
of $G$) gives a shortest path.

In the second step, we reduce the weighted version to the original unweighted
version of the problem. To this end, a vertex of weight $w$ is replicated by a
clique of size $w$. We want to make sure that a swap of the vertices $u,v$ of
weights $w(u),w(v)$, respectively in the weighted instance is mapped to
consecutive $w(u)\cdot w(v)$ swaps of the vertices of cliques that correspond
to $u$ and $v$ in the constructed unweighted instance. This is proved via the
useful operation of projections combined with the averaging argument.

##  2 Preliminaries

For a positive integer $k$, let $[k]$ denote $\\{1,2,\dots,k\\}$.

For a graph $G=(V,E)$ and two elimination trees $T_{\mathrm{ini}}$ and
$T_{\mathrm{tar}}$ of $G$, we say that a sequence $\mathbf{T}=\langle
T_{0},T_{1},\dots,T_{\ell}\rangle$ of elimination trees of $G$ is a
_reconfiguration sequence from $T_{\mathrm{ini}}$ to $T_{\mathrm{tar}}$_ if
$T_{0}=T_{\mathrm{ini}}$, $T_{\ell}=T_{\mathrm{tar}}$, and $T_{i}$ is obtained
from $T_{i-1}$ by applying a single swap operation for $i\in[\ell]$. We
sometimes regard $\mathbf{T}$ as a sequence of swap operations if no confusion
may arise. The length of $\mathbf{T}$ is defined as the number $\ell$ of swaps
in $\mathbf{T}$, which we denote $\mathrm{length}(\mathbf{T})$. Then,
Combinatorial Shortest Path on Graph Associahedra is the problem of finding a
reconfiguration sequence $\mathbf{T}$ from $T_{\mathrm{ini}}$ to
$T_{\mathrm{tar}}$ that minimizes $\mathrm{length}(\mathbf{T})$.

When $u\in V$ is a child of $v\in V$ in an elimination tree $T$, an operation
swapping $u$ and $v$ is represented by $\mathbf{swap}(u,v)$. Note that we
distinguish $\mathbf{swap}(u,v)$ and $\mathbf{swap}(v,u)$. For an elimination
tree $T$ and for a vertex $v\in V(T)$, let $\mathbf{anc}_{T}(v)$ (resp.
$\mathbf{des}_{T}(v)$) denote the set of all ancestors (descendants) of $v$ in
$T$. Note that $u\in\mathbf{anc}_{T}(v)$ if and only if
$v\in\mathbf{des}_{T}(u)$. Note also that neither $\mathbf{anc}_{T}(v)$ nor
$\mathbf{des}_{T}(v)$ contains $v$. We say that distinct vertices $u$ and $v$
are _comparable_ in $T$ if $u\in\mathbf{anc}_{T}(v)$ or
$v\in\mathbf{anc}_{T}(u)$. Otherwise, they are called _incomparable_ in $T$. A
linear ordering $\prec$ on $V$ defines an elimination tree $T$ uniquely so
that $u\in\mathbf{anc}_{T}(v)$ implies $u\prec v$.

Let $G=(V,E)$ be an undirected graph. For $X\subseteq V$, let $\delta_{G}(X)$
denote the set of edges between $X$ and $V\setminus X$. For $s,t\in V$, we say
that $X\subseteq V$ is an _$s$ -$t$ cut_ if $s\in X$ and $t\not\in X$. An edge
set $F\subseteq E$ is called an _$s$ -$t$ cut set_ if $F=\delta_{G}(X)$ for
some $s$-$t$ cut $X\subseteq V$. A _minimum $s$-$t$ cut_ is an $s$-$t$ cut $X$
minimizing $|\delta_{G}(X)|$. For $X\subseteq V$, let $G[X]$ denote the
subgraph induced by $X$ and let $E[X]$ denote its edge set.

##  3 Hardness of the Weighted Problem

We consider a weighted variant of Combinatorial Shortest Path on Graph
Associahedra, which we call Weighted Combinatorial Shortest Path on Graph
Associahedra. In the problem, we are given a graph $G=(V,E)$, two elimination
trees $T_{\mathrm{ini}}$ and $T_{\mathrm{tar}}$, and a weight function
$w\colon V\to\mathbb{Z}_{>0}$. For $u,v\in V$, the _weight_ of
$\mathbf{swap}(u,v)$ is defined as $w(u)\cdot w(v)$. This value is sometimes
denoted by $w(\mathbf{swap}(u,v))$. The _weighted length_ (or simply the
_weight_) of a reconfiguration sequence $\mathbf{T}$ is defined as the total
weight of swaps in $\mathbf{T}$, which we denote by
$\mathrm{length}_{w}(\mathbf{T})$. The objective of Weighted Combinatorial
Shortest Path on Graph Associahedra is to find a reconfiguration sequence
$\mathbf{T}$ from $T_{\mathrm{ini}}$ to $T_{\mathrm{tar}}$ that minimizes
$\mathrm{length}_{w}(\mathbf{T})$.

In this section, we show that the weighted variant is strongly
$\mathrm{NP}$-hard.

######  Theorem 3.1.

Weighted Combinatorial Shortest Path on Graph Associahedra is strongly
$\mathrm{NP}$-hard, that is, it is $\mathrm{NP}$-hard even when the input size
is $\sum_{v\in V}w(v)$.

###  3.1 Reduction

To show Theorem 3.1, we reduce Balanced Minimum $s$-$t$ Cut to Weighted
Combinatorial Shortest Path on Graph Associahedra. In Balanced Minimum $s$-$t$
Cut, the input consists of a connected graph $G=(V,E)$ with $s,t\in V$, and
the objective is to determine whether $G$ contains a minimum $s$-$t$ cut $X$
with $|X|=|V\setminus X|$. Without loss of generality, we may assume that
$|V|$ is even. Let $V=\\{s,t,v_{1},v_{2},\dots,v_{2n}\\}$ and
$E=\\{e_{1},\dots,e_{m}\\}$, where $|V|=2n+2$ and $|E|=m$. It is known that
Balanced Minimum $s$-$t$ Cut is $\mathrm{NP}$-hard [14]. For an instance of
Balanced Minimum $s$-$t$ Cut, we construct an instance of Weighted
Combinatorial Shortest Path on Graph Associahedra as follows.

Let $N$ be a sufficiently large integer (e.g., $N=10n^{3}m$). We first
subdivide each edge $e\in E$ by introducing a new vertex $u_{e}$. Then, for
each $v\in V$, we introduce a copy $v^{\prime}$ of $v$. We replace $s$ with a
clique $\\{s_{1},\dots,s_{N^{3}}\\}$ of size $N^{3}$ and replace $t$ with
another clique $\\{t_{1},\dots,t_{N^{3}}\\}$ of size $N^{3}$. Let $H$ be the
obtained graph. Formally, the graph $H=(V(H),E(H))$ is defined as follows:

$\displaystyle V(H)$ $\displaystyle=(V\setminus\\{s,t\\})\cup\\{v^{\prime}\mid
v\in V\\}\cup\\{u_{e}\mid e\in
E\\}\cup\\{s_{1},\dots,s_{N^{3}}\\}\cup\\{t_{1},\dots,t_{N^{3}}\\},$
$\displaystyle E(H)$ $\displaystyle=\\{\\{v,u_{e}\\}\mid v\in
V\setminus\\{s,t\\},\ e\in\delta_{G}(v)\\}\cup\\{\\{v^{\prime},u_{e}\\}\mid
v\in V,\ e\in\delta_{G}(v)\\}$ $\displaystyle\quad\cup\\{\\{s_{i},s_{j}\\}\mid
i,j\in[N^{3}],\ i\neq j\\}\cup\\{\\{t_{i},t_{j}\\}\mid i,j\in[N^{3}],\ i\neq
j\\}$ $\displaystyle\quad\cup\\{\\{s_{i},u_{e}\\}\mid i\in[N^{3}],\
e\in\delta_{G}(s)\\}\cup\\{\\{t_{i},u_{e}\\}\mid i\in[N^{3}],\
e\in\delta_{G}(t)\\}.$

Define $w\colon V(H)\to\mathbb{Z}_{>0}$ as follows:

$\displaystyle w(v)=N$ $\displaystyle(v\in V\setminus\\{s,t\\}),$
$\displaystyle w(v^{\prime})=N^{8}$ $\displaystyle(v\in V),$ $\displaystyle
w(u_{e})=1$ $\displaystyle(e\in E),$ $\displaystyle w(s_{i})=w(t_{i})=N^{4}$
$\displaystyle(i\in[N^{3}]).$

The initial elimination tree $T_{\mathrm{ini}}$ is defined by the following
linear ordering:

$\displaystyle v_{1}\prec\dots\prec v_{2n}\prec s_{1}\prec t_{1}\prec
s_{2}\prec t_{2}\prec\dots\prec s_{N^{3}}\prec t_{N^{3}}$
$\displaystyle\qquad\prec u_{e_{1}}\prec\dots\prec u_{e_{m}}\prec
v^{\prime}_{1}\prec\dots\prec v^{\prime}_{2n}\prec s^{\prime}\prec
t^{\prime}.$

Note that, in $T_{\mathrm{ini}}$, the vertices
$v_{1},\dots,v_{2n},s_{1},t_{1},s_{2},t_{2},\dots,s_{N^{3}},t_{N^{3}}$ are
aligned on a path, while the other elements are not necessarily aligned
sequentially. The target elimination tree $T_{\mathrm{tar}}$ is the
elimination tree defined by the following linear ordering:

$\displaystyle v_{2n}\prec\dots\prec v_{1}\prec t_{1}\prec s_{1}\prec
t_{2}\prec s_{2}\prec\dots\prec t_{N^{3}}\prec s_{N^{3}}$
$\displaystyle\qquad\prec u_{e_{1}}\prec\dots\prec u_{e_{m}}\prec
v^{\prime}_{1}\prec\dots\prec v^{\prime}_{2n}\prec s^{\prime}\prec
t^{\prime}.$

We consider an instance $(H,w,T_{\mathrm{ini}},T_{\mathrm{tar}})$ of Weighted
Combinatorial Shortest Path on Graph Associahedra. In this instance, we
reverse the ordering of the first $2n$ elements and reverse the ordering of
$s_{i}$ and $t_{i}$ for each $i$. See Figure 3 for an illustration.

Figure 3: Reduction for Theorem 3.1.

To prove Theorem 1.1, it suffices to show the following proposition.

######  Proposition 3.2.

Let $\lambda$ be the minimum size of an $s$-$t$ cut set in $G$. There is a
reconfiguration sequence from $T_{\mathrm{ini}}$ to $T_{\mathrm{tar}}$ of
weight less than $4\lambda N^{7}+(n^{2}-n+1)N^{2}$ if and only if $G$ has a
minimum $s$-$t$ cut $X$ with $|X|=|V\setminus X|$.

###  3.2 Proof of Proposition 3.2

#### Sufficiency (“if” part)

Suppose that $G$ has a minimum $s$-$t$ cut $X$ with $|X|=|V\setminus X|=n+1$.
Let $U=\\{u_{e}\mid e\in\delta_{G}(X)\\}$. Note that
$|U|=|\delta_{G}(X)|=\lambda$. Starting from $T_{\mathrm{ini}}$, we swap an
element in $U$ and its parent repeatedly so that we obtain an elimination tree
$T_{1}$ in which each element in $U$ is an ancestor of $V(H)\setminus U$. See
Figure 4. The total weight of swaps from $T_{\mathrm{ini}}$ to $T_{1}$ is at
most $|U|(2nN+2N^{7}+m)$. Since $G-\delta_{G}(X)$ consists of two connected
components, so does $H-U$. Thus, $T_{1}-U$ consists of two elimination trees
$T_{s}$ and $T_{t}$ such that $T_{s}$ contains
$(X\setminus\\{s\\})\cup\\{s_{1},\dots,s_{N^{3}}\\}\cup\\{u_{e}\mid e\in
E[X]\\}\cup\\{v^{\prime}\mid v\in X\\}$ and $T_{t}$ contains $((V\setminus
X)\setminus\\{t\\})\cup\\{t_{1},\dots,t_{N^{3}}\\}\cup\\{u_{e}\mid e\in
E[V\setminus X]\\}\cup\\{v^{\prime}\mid v\in V\setminus X\\}$.

Figure 4: A reconfiguration sequence from $T_{\mathrm{ini}}$ to
$T_{\mathrm{tar}}$.

In $T_{s}$, by swapping $u$ and $v$ for every pair of $u,v\in
X\setminus\\{s\\}$, we obtain an elimination tree in which $v_{i}$ is an
ancestor of $v_{j}$ for $v_{i},v_{j}\in X\setminus\\{s\\}$ with $i>j$. The
total weight of these swaps is $\binom{|X|-1}{2}\cdot N^{2}$. Similarly, by
applying swaps with weight $\binom{|V\setminus X|-1}{2}\cdot N^{2}$ to
$T_{t}$, we obtain an elimination tree in which $v_{i}$ is an ancestor of
$v_{j}$ for $v_{i},v_{j}\in(V\setminus X)\setminus\\{t\\}$ with $i>j$. Let
$T_{2}$ be the elimination tree obtained from $T_{1}$ by applying these
operations.

Starting from $T_{2}$, we swap an element in $U$ and its child repeatedly so
that we obtain an elimination tree $T_{\mathrm{tar}}$. This can be done by
applying swaps whose total weight is at most $|U|(2nN+2N^{7}+m)$.

Therefore, the total weight of the above swaps from $T_{\mathrm{ini}}$ to
$T_{\mathrm{tar}}$ is at most

$\displaystyle 2|U|(2nN+2N^{7}+m)+\binom{|X|-1}{2}\cdot
N^{2}+\binom{|V\setminus X|-1}{2}\cdot N^{2}$ $\displaystyle\quad=4\lambda
N^{7}+n(n-1)N^{2}+4\lambda nN+2\lambda m$ $\displaystyle\quad<4\lambda
N^{7}+(n^{2}-n+1)N^{2},$

where we note that $|U|=\lambda$ and $|X|=|V\setminus X|=n+1$. This shows the
sufficiency.

#### Necessity (“only if” part)

Let $\mathbf{T}$ be a reconfiguration sequence from $T_{\mathrm{ini}}$ to
$T_{\mathrm{tar}}$ whose weight is less than $4\lambda
N^{7}+(n^{2}-n+1)N^{2}$. Since this weight is less than $N^{8}$, we observe
the following. For $v\in V$, vertex $v^{\prime}$ is not swapped with other
vertices in $\mathbf{T}$. For $i,j\in[N^{3}]$, none of
$\mathbf{swap}(s_{i},s_{j})$, $\mathbf{swap}(t_{i},t_{j})$,
$\mathbf{swap}(s_{i},t_{j})$, and $\mathbf{swap}(t_{i},s_{j})$ is applied in
$\mathbf{T}$. By Observation 3.2, we cannot swap $s_{1}$ and $t_{1}$ directly,
and hence $\mathbf{T}$ contains an elimination tree $T^{*}$ in which $s_{1}$
and $t_{1}$ are incomparable. Then, there exists a vertex set $V^{*}\subseteq
V(H)$ such that $s_{1}$ and $t_{1}$ are contained in different connected
components of $H-V^{*}$, and each vertex in $V^{*}$ is an ancestor of $s_{1}$
and $t_{1}$ in $T^{*}$. By Observation 3.2 again, $V^{*}$ does not contain
$v^{\prime}$ for $v\in V$, that is, $V^{*}\subseteq V\cup\\{u_{e}\mid e\in
E\\}$. Note that removing $V^{*}\cap V$ does not affect the connectedness of
$H$ since each vertex $v\in V^{*}\cap V$ has its copy $v^{\prime}$ in $H$. Let

$F:=\\{e\in E\mid u_{e}\in V^{*}\\}.$

Then, $s$ and $t$ are contained in different connected components of $G-F$,
i.e., $F$ contains an $s$-$t$ cut set in $G$.

Since removing $V$ does not affect the connectedness of $H$, we also observe
the following. Let $T$ and $T^{\prime}$ be elimination trees in $\mathbf{T}$
and let $e_{1},e_{2}\in E$ be distinct edges. If
$u_{e_{1}}\in\mathbf{anc}_{T}(u_{e_{2}})$ and
$u_{e_{2}}\in\mathbf{anc}_{T^{\prime}}(u_{e_{1}})$, then
$\mathbf{swap}(u_{e_{3}},u_{e_{4}})$ is applied for some $e_{3},e_{4}\in E$
(possibly $\\{e_{1},e_{2}\\}\cap\\{e_{3},e_{4}\\}\neq\emptyset$) between $T$
and $T^{\prime}$.

We divide $\mathbf{T}$ into two reconfiguration sequences $\mathbf{T}_{1}$ and
$\mathbf{T}_{2}$, where $\mathbf{T}_{1}$ is from $T_{\mathrm{ini}}$ to $T^{*}$
and $\mathbf{T}_{2}$ is from $T^{*}$ to $T_{\mathrm{tar}}$. By symmetry, we
may assume that

$\mathrm{length}_{w}(\mathbf{T}_{1})\leq\frac{\mathrm{length}_{w}(\mathbf{T})}{2}<2\lambda
N^{7}+N^{3}.$

For $i\in[N^{3}]$, define

$\displaystyle L_{i}$ $\displaystyle=\\{e\in
E\mid\mathbf{swap}(u_{e},s_{i})\text{ is applied in }\mathbf{T}_{1}\\},$
$\displaystyle R_{i}$ $\displaystyle=\\{e\in
E\mid\mathbf{swap}(u_{e},t_{i})\text{ is applied in }\mathbf{T}_{1}\\}.$

For $i\in[N^{3}]$, let $\mathbf{swap}(L_{i})$ denote the set of all swaps
$\mathbf{swap}(u_{e},s_{i})$ in $\mathbf{T}_{1}$ with $e\in L_{i}$. Similarly,
let $\mathbf{swap}(R_{i})$ denote the set of all swaps
$\mathbf{swap}(u_{e},t_{i})$ in $\mathbf{T}_{1}$ with $e\in R_{i}$.

######  Claim 1.

For $i\in[N^{3}]$, we have the following:

  * •

if an edge $e\in E$ is contained in the connected component of $G-L_{i}$
containing $s$, then $u_{e}\in\mathbf{des}_{T}(s_{i})$ for any elimination
tree $T$ in $\mathbf{T}_{1}$, and

  * •

if an edge $e\in E$ is contained in the connected component of $G-R_{i}$
containing $t$, then $u_{e}\in\mathbf{des}_{T}(t_{i})$ for any elimination
tree $T$ in $\mathbf{T}_{1}$.

For each edge $e\in E$ in the connected component of $G-L_{i}$ containing $s$,
vertices $s_{i}$ and $u_{e}$ are contained in the same connected component in
$H-\\{u_{f}\mid f\in L_{i}\\}$. Since
$u_{e}\in\mathbf{des}_{T_{\mathrm{ini}}}(s_{i})$ holds and
$\mathbf{swap}(u_{e},s_{i})$ is not applied in $\mathbf{T}_{1}$ as $e\not\in
L_{i}$, we have that $u_{e}\in\mathbf{des}_{T}(s_{i})$ for any elimination
tree $T$ in $\mathbf{T}_{1}$. The same argument works for the second
statement.

To simplify the notation, let $L_{0}=R_{0}=F$. For $i\in[N^{3}]\cup\\{0\\}$,
let $X_{i}\subseteq V$ be the vertex set of the connected component of
$G-L_{i}$ containing $s$. Similarly, let $Y_{i}\subseteq V$ be the vertex set
of the connected component of $G-R_{i}$ containing $t$.

######  Claim 2.

For $i,j\in[N^{3}]\cup\\{0\\}$ with $j>i$, we have the following:

  1. (i)

$(E[X_{j}]\setminus L_{j})\cap L_{i}=\emptyset$, and

  2. (ii)

$(E[Y_{j}]\setminus R_{j})\cap R_{i}=\emptyset$.

To show (i), assume to the contrary that there exists $e\in(E[X_{j}]\setminus
L_{j})\cap L_{i}$ for some $j>i$. Note that $j\in[N^{3}]$. Since $e\in
E[X_{j}]\setminus L_{j}$, Claim 1 shows that $u_{e}\in\mathbf{des}_{T}(s_{j})$
for any elimination tree $T$ in $\mathbf{T}_{1}$. If $i\geq 1$, then since
$u_{e}\in\mathbf{des}_{T}(s_{j})$ and $s_{i}\in\mathbf{anc}_{T}(s_{j})$, we
see that $u_{e}$ and $s_{i}$ are not adjacent in $T$. This implies that
$\mathbf{swap}(u_{e},s_{i})$ is not applied in $\mathbf{T}_{1}$, which
contradicts $e\in L_{i}$. If $i=0$, then $e\in L_{0}=F$ implies that
$u_{e}\in\mathbf{anc}_{T^{*}}(s_{1})\subseteq\mathbf{anc}_{T^{*}}(s_{j})$,
which contradicts $u_{e}\in\mathbf{des}_{T}(s_{j})$ for any $T$. The same
argument works for (ii).

######  Claim 3.

$X_{0}\supseteq X_{1}\supseteq X_{2}\supseteq\dots\supseteq X_{N^{3}}$ and
$Y_{0}\supseteq Y_{1}\supseteq Y_{2}\supseteq\dots\supseteq Y_{N^{3}}$.

Let $i,j\in[N^{3}]\cup\\{0\\}$ be indices with $j>i$. Since
$(E[X_{j}]\setminus L_{j})\cap L_{i}=\emptyset$ by Claim 2 (i), all vertices
in $X_{j}$ are contained in the same connected component of $G-L_{i}$. Since
both $X_{i}$ and $X_{j}$ contain $s$, we obtain $X_{j}\subseteq X_{i}$. This
shows that $X_{0}\supseteq X_{1}\supseteq X_{2}\supseteq\dots\supseteq
X_{N^{3}}$. Similarly, we obtain $Y_{0}\supseteq Y_{1}\supseteq
Y_{2}\supseteq\dots\supseteq Y_{N^{3}}$.

######  Claim 4.

For $i\in[N^{3}]$, we have $|L_{i}|=|R_{i}|=\lambda$,
$L_{i}=\delta_{G}(X_{i})$, and $R_{i}=\delta_{G}(Y_{i})$.

Since $F$ contains an $s$-$t$ cut set, it holds that $X_{0}\subseteq
V\setminus\\{t\\}$. For $i\geq 1$, since $s\in X_{i}\subseteq X_{0}\subseteq
V\setminus\\{t\\}$ by Claim 3, we see that $\delta_{G}(X_{i})$ is an $s$-$t$
cut set contained in $L_{i}$. Similarly, $R_{i}$ contains an $s$-$t$ cut set
in $G$. Therefore, we obtain $|L_{i}|,|R_{i}|\geq\lambda$ for any
$i\in[N^{3}]$. By considering the weight of $\mathbf{T}_{1}$, we obtain

$\displaystyle 2\lambda N^{7}+N^{3}$
$\displaystyle>\mathrm{length}_{w}(\mathbf{T}_{1})$
$\displaystyle\geq\sum_{i=1}^{N^{3}}(w(s_{i})|L_{i}|+w(t_{i})|R_{i}|)$
$\displaystyle=2\lambda
N^{7}+N^{4}\sum_{i=1}^{N^{3}}((|L_{i}|-\lambda)+(|R_{i}|-\lambda)),$

which shows that $|L_{i}|=|R_{i}|=\lambda$ for any $i\in[N^{3}]$. Therefore,
each of $L_{i}$ and $R_{i}$ is a minimum $s$-$t$ cut set in $G$, and hence
$L_{i}=\delta_{G}(X_{i})$ and $R_{i}=\delta_{G}(Y_{i})$ hold.

Since the total weight of $\mathbf{swap}(L_{i})$ and $\mathbf{swap}(R_{i})$ is
at least $2\lambda N^{7}$ by this claim, we see that $u_{e}$ and $s_{i}$
(resp. $t_{i}$) are swapped exactly once in $\mathbf{T}_{1}$ for $e\in L_{i}$
(resp. $e\in R_{i}$) and for $i\in[N^{3}]$. For $i\in[N^{3}]$, let $T_{i}$
(resp. $T^{\prime}_{i}$) be the elimination tree that appears in
$\mathbf{T}_{1}$ after all the swaps in $\mathbf{swap}(L_{i})$ (resp.
$\mathbf{swap}(R_{i})$) are just applied.

######  Claim 5.

Elimination trees
$T^{\prime}_{N^{3}},T_{N^{3}},T^{\prime}_{N^{3}-1},T_{N^{3}-1},\dots,T^{\prime}_{1},T_{1}$
appear in this order in $\mathbf{T}_{1}$.

We first show that $T_{i}$ appears after $T^{\prime}_{i}$ for $i\in[N^{3}]$.
Let $e\in R_{i}$ be the edge such that $\mathbf{swap}(u_{e},t_{i})$ is applied
just before obtaining $T^{\prime}_{i}$. Ler $f\in
L_{i}\setminus(R_{i}\setminus\\{e\\})$, where the existence of such $f$ is
guaranteed by $|L_{i}|=|R_{i}|$. Since $R_{i}$ is a minimum $s$-$t$ cut set by
Claim 4, we see that $G-(R_{i}\setminus\\{e\\})$ is connected. Then, for any
elimination tree $T$ before $T^{\prime}_{i}$, we have
$u_{e^{\prime}}\in\mathbf{des}_{T}(t_{i})$ for any $e^{\prime}\in
E\setminus(R_{i}\setminus\\{e\\})$. In particular,
$u_{f}\in\mathbf{des}_{T}(t_{i})$. Since $s_{i}\in\mathbf{anc}_{T}(t_{i})$, we
see that $u_{f}$ and $s_{i}$ are not adjacent in $T$. This shows that we
cannot apply $\mathbf{swap}(u_{f},s_{i})$ before $T^{\prime}_{i}$. Therefore,
$T_{i}$ appears after $T^{\prime}_{i}$ in $\mathbf{T}_{1}$.

By the same argument, we can show that $T^{\prime}_{i}$ appears after
$T_{i+1}$ for $i\in[N^{3}-1]$. Therefore, $T^{\prime}_{N^{3}}$, $T_{N^{3}}$,
$T^{\prime}_{N^{3}-1}$, $T_{N^{3}-1},\dots,T^{\prime}_{1}$, $T_{1}$ appear in
this order.

######  Claim 6.

For $i\in[N^{3}]$, we have the following:

  * •

$u_{e}\in\mathbf{anc}_{T_{i}}(u_{e^{\prime}})$ for any $e\in L_{i}$ and
$e^{\prime}\in E\setminus L_{i}$, and

  * •

$u_{e}\in\mathbf{anc}_{T^{\prime}_{i}}(u_{e^{\prime}})$ for any $e\in R_{i}$
and $e^{\prime}\in E\setminus R_{i}$.

Let $T$ be an elimination tree in $\mathbf{T}_{1}$ just before $T_{i}$. Then,
there exists an edge $f\in L_{i}$ such that $T_{i}$ is obtained from $T$ by
applying $\mathbf{swap}(u_{f},s_{i})$. Since $G-(L_{i}\setminus\\{f\\})$ is
connected by Claim 4, we have $u_{e}\in\mathbf{anc}_{T}(s_{i})$ for $e\in
L_{i}\setminus\\{f\\}$ and $u_{e^{\prime}}\in\mathbf{des}_{T}(s_{i})$ for
$e^{\prime}\in E\setminus(L_{i}\setminus\\{f\\})$. Therefore, after applying
$\mathbf{swap}(u_{f},s_{i})$, we obtain $u_{e}\in\mathbf{anc}_{T_{i}}(f)$ for
$e\in L_{i}\setminus\\{f\\}$ and $u_{e^{\prime}}\in\mathbf{des}_{T_{i}}(f)$
for $e^{\prime}\in E\setminus L_{i}$. This shows that
$u_{e}\in\mathbf{anc}_{T_{i}}(u_{e^{\prime}})$ for any $e\in L_{i}$ and
$e^{\prime}\in E\setminus L_{i}$. By the same argument, we obtain
$u_{e}\in\mathbf{anc}_{T^{\prime}_{i}}(u_{e^{\prime}})$ for any $e\in R_{i}$
and $e^{\prime}\in E\setminus R_{i}$.

######  Claim 7.

$X_{1}=V\setminus Y_{1}$.

Observe that $X_{0}$ and $Y_{0}$ are disjoint since $F=L_{0}=R_{0}$ contains
an $s$-$t$ cut set in $G$. Since $X_{1}\subseteq X_{0}$ and $Y_{1}\subseteq
Y_{0}$ by Claim 3, we see that $X_{1}$ and $Y_{1}$ are disjoint. To derive a
contradiction, assume that $X_{1}\neq V\setminus Y_{1}$, that is, $X_{1}$ and
$Y_{1}$ are disjoint sets with $X_{1}\cup Y_{1}\subsetneq V$. Then, by Claim
3, we obtain $X_{i}\neq V\setminus Y_{i}$ for any $i\in[N^{3}]$. This shows
that $L_{i}\neq R_{i}$ for any $i\in[N^{3}]$. Since $|L_{i}|=|R_{i}|=\lambda$,
there exist $f_{i}\in L_{i}\setminus R_{i}$ and $f^{\prime}_{i}\in
R_{i}\setminus L_{i}$. By Claim 6, we obtain
$u_{f_{i}}\in\mathbf{anc}_{T_{i}}(u_{f^{\prime}_{i}})$ and
$u_{f^{\prime}_{i}}\in\mathbf{anc}_{T^{\prime}_{i}}(u_{f_{i}})$. By
Observation 3.2, $\mathbf{swap}(u_{e},u_{e^{\prime}})$ is applied for some
$e,e^{\prime}\in E$ between $T^{\prime}_{i}$ and $T_{i}$. Since such a swap is
required for each $i\in[N^{3}]$, by Claim 5, we have to swap pairs in
$\\{u_{e}\mid e\in E\\}$ at least $N^{3}$ times in $\mathbf{T}_{1}$.
Therefore, we obtain

$\mathrm{length}_{w}(\mathbf{T}_{1})\geq\sum_{i=1}^{N^{3}}(w(s_{i})|L_{i}|+w(t_{i})|R_{i}|)+N^{3}=2\lambda
N^{7}+N^{3},$

which contradicts $\mathrm{length}_{w}(\mathbf{T}_{1})<2\lambda N^{7}+N^{3}$.

######  Claim 8.

$F=\delta_{G}(X_{1})=\delta_{G}(Y_{1})$.

Claims 4 and 7 show that $L_{1}=R_{1}=\delta_{G}(X_{1})=\delta_{G}(Y_{1})$.
This together with Claim 2 shows that $F\cap E[X_{1}]=F\cap
E[Y_{1}]=\emptyset$. Since $F$ contains an $s$-$t$ cut set in $G$, we obtain
$F=\delta_{G}(X_{1})=\delta_{G}(Y_{1})$.

######  Claim 9.

Let $T$ be an elimination tree in $\mathbf{T}_{1}$. If two vertices $u,v\in
V\setminus\\{s,t\\}$ are contained in the same connected component in $G-F$,
then $u$ and $v$ are comparable in $T$.

By Claim 8, $G-F$ consists of two connected components $G[X_{1}]$ and
$G[Y_{1}]$. We first consider the case when $u,v\in X_{1}\setminus\\{s\\}$. By
Claims 1 and 8, we obtain $u_{e}\in\mathbf{des}_{T}(s_{1})$ for any $e\in
E[X_{1}]$. Furthermore, since $\mathrm{length}_{w}(\mathbf{T}_{1})<2\lambda
N^{7}+N^{3}$ holds and the total weight of $\mathbf{swap}(L_{i})$ and
$\mathbf{swap}(R_{i})$ is $2\lambda N^{7}$, neither $\mathbf{swap}(s_{1},u)$
nor $\mathbf{swap}(s_{1},v)$ is applied in $\mathbf{T}_{1}$, because
$w(s_{1})w(u)=w(s_{1})w(v)=N^{5}$. Therefore, we obtain
$u\in\mathbf{anc}_{T}(s_{1})$ and $v\in\mathbf{anc}_{T}(s_{1})$, which shows
that $u$ and $v$ are comparable in $T$. The same argument works when $u,v\in
Y_{1}\setminus\\{t\\}$.

Since the weight of $\mathbf{T}_{1}$ is at least
$\sum_{i=1}^{N^{3}}(w(s_{i})|L_{i}|+w(t_{i})|R_{i}|)=2\lambda N^{7}$, we
obtain

$\mathrm{length}_{w}(\mathbf{T}_{2})=\mathrm{length}_{w}(\mathbf{T})-\mathrm{length}_{w}(\mathbf{T}_{1})<2\lambda
N^{7}+N^{3}.$

Hence, the above argument (Claims 1–9) can be applied also to the reverse
sequence of $\mathbf{T}_{2}$. In particular, Claim 9 holds even if
$\mathbf{T}_{1}$ is replaced with $\mathbf{T}_{2}$. Therefore, if two vertices
$u,v\in V\setminus\\{s,t\\}$ are contained in the same connected component in
$G-F$, then $u$ and $v$ are comparable in any elimination tree in
$\mathbf{T}$. For such a pair of vertices $u$ and $v$, the only way to reverse
the ordering of $u$ and $v$ is to apply $\mathbf{swap}(u,v)$ or
$\mathbf{swap}(v,u)$.

Recall that $G-F$ consists of two connected components $G[X_{1}]$ and
$G[Y_{1}]$ by Claim 8. Since the ordering of $v_{1},\dots,v_{2n}$ are reversed
from $T_{\mathrm{ini}}$ to $T_{\mathrm{tar}}$, we see that
$\mathbf{swap}(u,v)$ or $\mathbf{swap}(v,u)$ has to be applied in $\mathbf{T}$
if $u,v\in X_{1}\setminus\\{s\\}$ or $u,v\in Y_{1}\setminus\\{t\\}=(V\setminus
X_{1})\setminus\\{t\\}$. Furthermore, we have to swap some elements in
$\\{u_{e}\mid e\in E\\}$ and $\\{s_{1},t_{1},\dots,s_{N^{3}},t_{N^{3}}\\}$ in
$\mathbf{T}_{2}$, whose total weight is at least $2\lambda N^{7}$ in the same
way as $\mathbf{T}_{1}$. With these observations, we evaluate the weight of
$\mathbf{T}$ as follows, where we denote $k=|X_{1}|$ to simplify the notation:

$\displaystyle\mathrm{length}_{w}(\mathbf{T})$ $\displaystyle\geq 2\lambda
N^{7}+2\lambda N^{7}+\binom{|X_{1}|-1}{2}\cdot N^{2}+\binom{|V\setminus
X_{1}|-1}{2}\cdot N^{2}$ $\displaystyle=4\lambda
N^{7}+\frac{(k-1)(k-2)}{2}N^{2}+\frac{(2n-k+1)(2n-k)}{2}N^{2}$
$\displaystyle=4\lambda N^{7}+(k^{2}-2(n+1)k+2n^{2}+n+1)N^{2}$
$\displaystyle=4\lambda N^{7}+(n^{2}-n)N^{2}+(k-n-1)^{2}N^{2}.$

This together with $\mathrm{length}_{w}(\mathbf{T})<4\lambda
N^{7}+(n^{2}-n+1)N^{2}$ shows that $(k-n-1)^{2}<1$, and hence $k=n+1$ by the
integrality of $k$ and $n$.

Therefore, we obtain $|X_{1}|=k=n+1$ and $|Y_{1}|=|V\setminus X_{1}|=n+1$.
Since $|\delta_{G}(X_{1})|=|L_{1}|=\lambda$, this shows that $X_{1}$ is a
desired $s$-$t$ cut in $G$.

##  4 Hardness of the Unweighted Problem (Proof of Theorem 1.1)

To show Theorem 1.1, we reduce Weighted Combinatorial Shortest Path on Graph
Associahedra to Combinatorial Shortest Path on Graph Associahedra. An
operation called _projection_ (e.g. [6]) plays an important role in our
validity proof.

###  4.1 Useful Operation: Projection

Let $G=(V,E)$ be a graph and let $T$ be an elimination tree associated with
$G$. For $U\subseteq V$ such that $G[U]$ is connected, let $T|_{U}$ be the
elimination tree associated with $G[U]$ that preserves the ordering in $T$.
That is, $u\in\mathbf{anc}_{T|_{U}}(v)$ if and only if
$u\in\mathbf{anc}_{T}(v)$ and $u$ are $v$ are connected in
$G[U]-\mathbf{anc}_{T}(u)$ for $u,v\in U$. Note that such $T|_{U}$ is uniquely
determined. We call $T|_{U}$ the _projection_ of $T$ to $U$. See Figure 5 for
illustration.

Figure 5: An example of projections. Note that
$T|_{\\{b,c,d\\}}=T^{\prime}|_{\\{b,c,d\\}}$ since $b$ and $c$ are
incomparable in $T|_{\\{b,c,d\\}}$, and $T^{\prime\prime}|_{\\{d,f,g\\}}$ is
obtained from $T^{\prime}|_{\\{d,f,g\\}}$ by swapping $f$ and $g$ since $f$
and $g$ are adjacent in $T^{\prime}|_{\\{d,f,g\\}}$.

######  Lemma 4.1.

Let $U\subseteq V$ be a vertex set such that $G[U]$ is connected. Let $T$ and
$T^{\prime}$ be elimination trees associated with $G$ such that $T^{\prime}$
is obtained from $T$ by applying $\mathbf{swap}(u,v)$, where $u,v\in V$.

  1. 1.

If $\\{u,v\\}\subseteq U$, then either $T^{\prime}|_{U}=T|_{U}$ or
$T^{\prime}|_{U}$ is obtained from $T|_{U}$ by applying $\mathbf{swap}(u,v)$.

  2. 2.

Otherwise, $T^{\prime}|_{U}=T|_{U}$.

######  Proof 4.2.

Since all the vertices in $V\setminus U$ are removed when we construct
$T|_{U}$, $\mathbf{swap}(u,v)$ affects $T|_{U}$ only if $\\{u,v\\}\subseteq
U$, which proves the second item. For the first item, suppose that
$\\{u,v\\}\subseteq U$. Then, $u$ and $v$ are adjacent or incomparable in
$T|_{U}$. If they are adjacent, then $T^{\prime}|_{U}$ is obtained from
$T|_{U}$ by applying $\mathbf{swap}(u,v)$. If they are incomparable, then
$T^{\prime}|_{U}=T|_{U}$.

###  4.2 Reduction

Suppose we are given a graph $G=(V,E)$, two elimination trees
$T_{\mathrm{ini}}$ and $T_{\mathrm{tar}}$, and a weight function $w\colon
V\to\mathbb{Z}_{>0}$, which form an instance of Weighted combinatorial
Shortest Path on Graph Associahedra. Then, we replace each vertex $v\in V$
with a clique of size $w(v)$. Formally, consider a graph
$G^{\prime}=(V^{\prime},E^{\prime})$ such that $V^{\prime}=\\{v_{i}\mid v\in
V,\ i\in\\{1,\dots,w(v)\\}\\}$, and $\\{u_{i},v_{j}\\}\in E^{\prime}$ if
$\\{u,v\\}\in E$ or $u=v$. Let $T^{\prime}_{\mathrm{ini}}$ (resp.
$T^{\prime}_{\mathrm{tar}}$) be the elimination tree obtained from
$T_{\mathrm{ini}}$ (resp. $T_{\mathrm{tar}}$) by replacing a vertex $v\in V$
with a path $v_{1},v_{2},\dots,v_{w(v)}$. That is, for distinct $u,v\in V$,
there is an arc $(u,v)$ in $T_{\mathrm{ini}}$ (resp. $T_{\mathrm{tar}}$) if
and only if $(u_{w(u)},v_{1})$ is an arc of $T^{\prime}_{\mathrm{ini}}$ (resp.
$T^{\prime}_{\mathrm{tar}}$). Note that the obtained elimination tree is
associated with $G^{\prime}$. This defines an instance of Combinatorial
Shortest on Graph Associahedra.

###  4.3 Validity

In what follows, we show that the obtained instance of Combinatorial Shortest
Path on Graph Associahedra has a reconfiguration sequence of length at most
$\ell$ if and only if the original instance of Weighted Combinatorial Shortest
Path on Graph Associahedra has a reconfiguration sequence $\mathbf{T}$ with
$\mathrm{length}_{w}(\mathbf{T})\leq\ell$.

#### Sufficiency (“if” part)

Suppose that the original instance of Weighted Combinatorial Shortest Path on
Graph Associahedra has a reconfiguration sequence $\mathbf{T}$ from
$T_{\mathrm{ini}}$ to $T_{\mathrm{tar}}$. Then, we construct a reconfiguration
sequence $\mathbf{T}^{\prime}$ from $T^{\prime}_{\mathrm{ini}}$ to
$T^{\prime}_{\mathrm{tar}}$ by replacing each swap $\mathbf{swap}(u,v)$ in
$\mathbf{T}$ with $w(u)\cdot w(v)$ swaps $\\{\mathbf{swap}(u_{i},v_{j})\mid
i\in[w(u)],\ j\in[w(v)]\\}$. This gives a reconfiguration sequence from
$T^{\prime}_{\mathrm{ini}}$ to $T^{\prime}_{\mathrm{tar}}$ whose length is
$\mathrm{length}_{w}(\mathbf{T})$, which shows the sufficiency.

#### Necessity (“only if” part)

Suppose that the obtained instance of Combinatorial Shortest Path on Graph
Associahedra has a reconfiguration sequence $\mathbf{T}^{\prime}$ from
$T^{\prime}_{\mathrm{ini}}$ to $T^{\prime}_{\mathrm{tar}}$ of length at most
$\ell$. For any $v\in V$, since $v_{1},\dots,v_{w(v)}$ form a clique, they are
comparable in any elimination tree in $\mathbf{T}^{\prime}$. Furthermore,
since $v_{1},\dots,v_{w(v)}$ are aligned in this order in both
$T^{\prime}_{\mathrm{ini}}$ and $T^{\prime}_{\mathrm{tar}}$, we may assume
that $\mathbf{swap}(v_{i},v_{j})$ is not applied in $\mathbf{T}^{\prime}$ for
any $i,j\in[w(v)]$.

Let $\Phi$ be the set of all maps $\phi\colon V\to\mathbb{Z}$ such that
$\phi(v)\in\\{1,\dots,w(v)\\}$ for any $v\in V$. Note that $|\Phi|=\prod_{v\in
V}w(v)$. For $\phi\in\Phi$, define $U_{\phi}=\\{v_{\phi(v)}\mid v\in V\\}$.
Note that $G^{\prime}[U_{\phi}]$ is isomorphic to $G$, and hence it is
connected. By projecting each elimination tree in $\mathbf{T}^{\prime}$ to
$U_{\phi}$, we obtain a sequence of elimination trees. Lemma 4.1 shows that
this forms a reconfiguration sequence, say $\mathbf{T}_{\phi}$, if we remove
duplications when the same elimination tree appears consecutively. Since
$G^{\prime}[U_{\phi}]$ is isormorphic to $G$, by idenfitying $v_{\phi(v)}$
with $v$ for each $v\in V$, we can regard $\mathbf{T}_{\phi}$ as a
recofiguration sequence from $T_{\mathrm{ini}}$ to $T_{\mathrm{tar}}$. That
is, $\mathbf{T}_{\phi}$ is regarded as a feasible solution of the original
instance of Weighted Combinatorial Shortest Path on Graph Associahedra.

In what follows, we consider reconfiguration sequences
$\\{\mathbf{T}_{\phi}\mid\phi\in\Phi\\}$ and show that a desired sequence
exists among them. Suppose that $\mathbf{swap}(u_{i},v_{j})$ is applied in
$\mathbf{T}^{\prime}$, where $u,v\in V$, $i\in[w(u)]$, and $j\in[w(v)]$. Then,
Lemma 4.1 shows that the corresponding swap operation
$\mathbf{swap}(u_{i},v_{j})$, which is identified with $\mathbf{swap}(u,v)$,
is applied in $\mathbf{T}_{\phi}$ only if $\phi(u)=i$ and $\phi(v)=j$. Thus,
such a swap is applied in at most $|\\{\phi\in\Phi\mid\phi(u)=i,\
\phi(v)=j\\}|=|\Phi|/(w(u)\cdot w(v))$ sequences in
$\\{\mathbf{T}_{\phi}\mid\phi\in\Phi\\}$. Therefore, we obtain

$\displaystyle\sum_{\phi\in\Phi}\mathrm{length}_{w}(\mathbf{T}_{\phi})$
$\displaystyle=\sum_{\phi\in\Phi}\sum_{\mathbf{swap}(u,v)\in\mathbf{T}_{\phi}}w(\mathbf{swap}(u,v))$
$\displaystyle\leq\sum_{\mathbf{swap}(u_{i},v_{j})\in\mathbf{T}^{\prime}}w(\mathbf{swap}(u,v))\cdot\frac{|\Phi|}{w(u)\cdot
w(v)}$
$\displaystyle=\mathrm{length}(\mathbf{T}^{\prime})\cdot|\Phi|\leq\ell\cdot|\Phi|,$

where each reconfiguration sequence is regarded as a multiset of swaps.
Therefore,

$\min_{\phi\in\Phi}(\mathrm{length}_{w}(\mathbf{T}_{\phi}))\leq\frac{1}{|\Phi|}\sum_{\phi\in\Phi}\mathrm{length}_{w}(\mathbf{T}_{\phi})\leq\ell.$

Hence, there exists $\phi\in\Phi$ such that $\mathbf{T}_{\phi}$ is a desired
sequence. This shows the necessity.

Therefore, the weighted problem can be reduced to the unweighted problem, and
hence Theorem 3.1 implies Theorem 1.1.

##  5 Hardness for Polymatroids (Proof of Theorem 1.2)

In this section, we prove Theorem 1.2. We reduce Combinatorial Shortest Path
on Graph Associahedra to Combinatorial Shortest Path on Polymatroids. Assume
that we are given an instance $G=(V,E)$, $T_{\mathrm{ini}}$, and
$T_{\mathrm{tar}}$ of Combinatorial Shortest Path on Graph Associahedra. To
this end, we construct a polymatroid $(V,f)$ satisfying the following
conditions.

  1. 1.

$\mathbf{B}(f)$ is a realization of the $G$-associahedron.

  2. 2.

For each subset $X\subseteq V$, we can evaluate the value $f(X)$ in time
bounded by a polynomial in the size of $G$.

  3. 3.

We can find the extreme points $x_{\mathrm{ini}},x_{\mathrm{tar}}$ of
$\mathbf{B}(f)$ corresponding to $T_{\mathrm{ini}},T_{\mathrm{tar}}$,
respectively, in time bounded by a polynomial in the size of $G$.

We first argue that the conditions above suffice for our proof. Suppose the
existence of a polymatroid $(V,f)$ with the properties above. Then, we may
construct a polynomial-time algorithm for Combinatorial Shortest Path on Graph
Associahedra with a fictitious polynomial-time algorithm for Combinatorial
Shortest Path on Polymatroids as follows. Let
$(G,T_{\mathrm{ini}},T_{\mathrm{tar}})$ be an instance of Combinatorial
Shortest Path on Graph Associahedra. From Properties 1 and 3, we can construct
an instance $((V,f),x_{\mathrm{ini}},x_{\mathrm{tar}})$ of Combinatorial
Shortest Path on Polymatroids in polynomial time. By the fictitious
polynomial-time algorithm, we can solve the instance in time bounded by a
polynomial in $|V|$ and the number of oracle calls to $f$. By Property 2, this
running time is bounded by a polynomial in $|V|$. Thus, we find a solution to
$(G,T_{\mathrm{ini}},T_{\mathrm{tar}})$ in polynomial time, and the proof is
completed.

In our construction of such a polymatroid $(V,f)$, we use the realization of
the $G$-associahedron by Devadoss [12], which can be described as follows.

Let $G=(V,E)$ be a connected undirected graph with at least two vertices. We
define $n:=|V|$. For each subset $X\subseteq V$, we call a connected
component444More precisely speaking, $C$ is the vertex set of a connected
component. $C$ of $G-X$ a _non-trivial_ (resp.  _trivial_) connected component
if $|C|\geq 2$ (resp. $|C|=1$). For each subset $X\subseteq V$, we define
$\mathcal{C}^{\ast}(X)$ as the set of non-trivial connected components of
$G-X$.

Let $T$ be an elimination tree of $G$. For each vertex $v\in V$, we define
$T(v)$ as the vertex set of the subtree of $T$ rooted at $v$. Then, we define
the vector $x^{T}\in\mathbb{R}^{V}$ by choosing the coordinate $x^{T}(v)$ at
every vertex of $v$ from the leaves to the root according to the following
rule.

  * •

If $v$ is a leaf of $T$, then we define $x^{T}(v):=0$.

  * •

If $v$ is not a leaf of $T$, then we define $x^{T}(v)$ so that

$\sum_{u\in T(v)}x^{T}(u)=3^{|T(v)|-2}.$

Define $\mathcal{E}:=\\{x^{T}\in\mathbb{R}^{V}\mid\text{$T$ is an elimination
tree of $G$}\\}$.

######  Lemma 5.1 (Devadoss [12]).

The convex hull of $\mathcal{E}$ is a realization of the $G$-associahedron.
For each elimination tree $T$ of $G$, the point $x^{T}$ is an extreme point of
the $G$-associahedron.

Define the function $f\colon 2^{V}\to\mathbb{R}$ by

$f(X):=\displaystyle{3^{n-2}-\sum_{C\in\mathcal{C}^{\ast}(X)}3^{|C|-2}}$ (1)

for each subset $X\subseteq V$. Notice that since $n\geq 2$ and $G$ is
connected, $f(\emptyset)=0$. It is not difficult to see that we can evaluate
the values of the function $f$ in time bounded by a polynomial in the size of
$G$.

######  Lemma 5.2.

Let $a_{1},a_{2},\dots,a_{k}$ be positive integers. Then

$3^{a_{1}+a_{2}+\dots+a_{k}}\geq 3^{a_{1}}+3^{a_{2}}+\dots+3^{a_{k}}.$

######  Proof 5.3.

When $k=1$, this statement holds by definition.

In what follows, we prove that for every integer $k\geq 2$,

$3^{a_{1}+a_{2}+\dots+a_{k}}-(3^{a_{1}}+3^{a_{2}}+\dots+3^{a_{k}})\geq 3.$ (2)

First, we consider the case where $k=2$. In this case, since $a_{1},a_{2}\geq
1$, we have

$3^{a_{1}+a_{2}}-(3^{a_{1}}+3^{a_{2}})=(3^{a_{1}}-1)(3^{a_{2}}-1)-1\geq 3.$

Let $\ell\geq 2$ be a positive integer, and assume that (2) holds when
$k=\ell$. Then, we consider the case where $k=\ell+1$. Since
$a_{1},a_{2},\dots,a_{\ell+1}$ are positive integers, we have

$\begin{split}&3^{a_{1}+a_{2}+\dots+a_{\ell+1}}-(3^{a_{1}}+3^{a_{2}}+\dots+3^{a_{\ell+1}})\\\
&=3^{a_{\ell+1}}\cdot
3^{a_{1}+a_{2}+\dots+a_{\ell}}-(3^{a_{1}}+3^{a_{2}}+\dots+3^{a_{\ell+1}})\\\
&\geq
3^{a_{\ell+1}}(3^{a_{1}}+3^{a_{2}}+\dots+3^{a_{\ell}}+3)-(3^{a_{1}}+3^{a_{2}}+\dots+3^{a_{\ell+1}})\\\
&=(3^{a_{1}+a_{\ell+1}}+3^{a_{2}+a_{\ell+1}}+\dots+3^{a_{\ell}+a_{\ell+1}}+3^{a_{\ell+1}+1})-(3^{a_{1}}+3^{a_{2}}+\dots+3^{a_{\ell+1}})\\\
&\geq 3^{a_{\ell+1}}(3-1)\geq 3,\end{split}$

where the first inequality follows from the induction hypothesis. This
completes the proof.

######  Lemma 5.4.

The function $f$ defined in (1) satisfies (P1), (P2), and (P3).

Here, we recall the three properties: (P1) $f(\emptyset)=0$; (P2) If
$X\subseteq Y\subseteq V$, then $f(X)\leq f(Y)$; (P3) If $X,Y\subseteq V$,
then $f(X\cup Y)+f(X\cap Y)\leq f(X)+f(Y)$.

######  Proof 5.5.

The property (P1) readily follows from the definition of $f$. Thus, we
consider (P2) and (P3).

We first prove (P2). Let $X$ be a subset $V$, and let $v$ be a vertex in
$V\setminus X$. It is sufficient to prove that $f(X)\leq f(X\cup\\{v\\})$. Let
$C_{1},C_{2},\dots,C_{k}$ be the non-trivial connected components of $G-X$.
Then we have

$f(X)=3^{n-2}-\sum_{i=1}^{k}3^{|C_{i}|-2}.$

If $v\notin\bigcup_{i=1}^{k}C_{i}$, then $v$ is an isolated vertex of $G-X$.
This implies that ${\cal C}^{\ast}(X)={\cal C}^{\ast}(X\cup\\{v\\})$. Thus,
$f(X)=f(X\cup\\{v\\})$. From here, we assume that
$v\in\bigcup_{i=1}^{k}C_{i}$. Without loss of generality, we assume that $v\in
C_{k}$. Then, $C_{k}\setminus\\{v\\}$ is partitioned into connected components
$C^{\prime}_{1},C^{\prime}_{2},\dots,C^{\prime}_{\ell}$ of $G-(X\cup\\{v\\})$.
Assume that $C^{\prime}_{1},C^{\prime}_{2},\dots,C^{\prime}_{t}$ are non-
trivial, and $C^{\prime}_{t+1},C^{\prime}_{t+2},\dots,C^{\prime}_{\ell}$ are
trivial. Then, we have

$f(X\cup\\{v\\})=3^{n-2}-\sum_{i=1}^{k-1}3^{|C_{i}|-2}-\sum_{i=1}^{t}3^{|C^{\prime}_{i}|-2}.$

Since $|C_{k}|>\sum_{i=1}^{t}|C^{\prime}_{i}|$, we have

$\begin{split}f(X\cup\\{v\\})-f(X)=3^{|C_{k}|-2}-\sum_{i=1}^{t}3^{|C_{i}|-2}\geq
3^{\sum_{i=1}^{t}|C^{\prime}_{i}|-2}-\sum_{i=1}^{t}3^{|C^{\prime}_{i}|-2}\geq
0,\end{split}$

where the first inequality follows from the monotonicity of the function
$g(x)=3^{x-2}$, and the second inequality follows from Lemma 5.2.

Next, we prove (P3). Let $X$ be a subset of $V$. Let $u,v$ be distinct
vertices in $V\setminus X$. Then it is sufficient to prove that

$f(X\cup\\{u\\})+f(X\cup\\{v\\})\geq f(X\cup\\{u,v\\})+f(X).$

(See e.g., [16, p.58].) Let $C_{1},C_{2},\dots,C_{k}$ be the non-trivial
connected components of $G-X$. Then, we have

$f(X)=3^{n-2}-\sum_{i=1}^{k}3^{|C_{i}|-2}.$

First, we consider the case where $u\notin\bigcup_{i=1}^{k}C_{i}$. In this
case, since $u$ is an isolated vertex in $G-X$, we have $f(X)=f(X\cup\\{u\\})$
and $f(X\cup\\{v\\})=f(X\cup\\{u,v\\})$. Similarly, we can treat the case
where $v\notin\bigcup_{i=1}^{k}C_{i}$.

Next, we consider the case where $u,v\in\bigcup_{i=1}^{k}C_{i}$, and $u,v$
belong to distinct connected components of $G-X$. Without loss of generality,
we assume that $u\in C_{k-1}$ and $v\in C_{k}$.

  * •

Let $C^{\circ}_{1},C^{\circ}_{2},\dots,C^{\circ}_{\ell}$ be the non-trivial
connected components of $G[C_{k-1}]-\\{u\\}$, where $G[C_{k-1}]$ denotes the
subgraph of $G$ induced by $C_{k-1}$.

  * •

Let $C^{\bullet}_{1},C^{\bullet}_{2},\dots,C^{\bullet}_{t}$ be the non-trivial
connected components of $G[C_{k}]-\\{v\\}$.

Then, the non-trivial connected components of $G[C_{k-1}\cup C_{k}]-\\{u,v\\}$
are
$C^{\circ}_{1},\dots,C^{\circ}_{\ell},C^{\bullet}_{1},\dots,C^{\bullet}_{t}$.
Thus, we have

$f(X\cup\\{u\\})+f(X\cup\\{v\\})=f(X\cup\\{u,v\\})+f(X).$

Finally, we consider the case where $u,v\in\bigcup_{i=1}^{k}C_{i}$, and $u,v$
belong to the same connected component of $G-X$. Without loss of generality,
we assume that $u,v\in C_{k}$.

  * •

Let $C^{\circ}_{1},C^{\circ}_{2},\dots,C^{\circ}_{\ell}$ be the non-trivial
connected components of $G[C_{k}]-\\{u\\}$.

  * •

Let $C^{\bullet}_{1},C^{\bullet}_{2},\dots,C^{\bullet}_{t}$ be the non-trivial
connected components of $G[C_{k}]-\\{v\\}$.

  * •

Let $C^{\prime}_{1},C^{\prime}_{2},\dots,C^{\prime}_{m}$ be the non-trivial
connected components of $G[C_{k}]-\\{u,v\\}$.

Then, since $\sum_{i=1}^{\ell}|C_{i}^{\circ}|\leq|C_{k}|-1$ and
$\sum_{i=1}^{t}|C_{i}^{\bullet}|\leq|C_{k}|-1$, we have

$\begin{split}&f(X\cup\\{u\\})+f(X\cup\\{v\\})-f(X\cup\\{u,v\\})-f(X)\\\
&={}-\sum_{i=1}^{\ell}3^{|C^{\circ}_{i}|-2}-\sum_{i=1}^{t}3^{|C^{\bullet}_{i}|-2}+3^{|C_{k}|-2}+\sum_{i=1}^{m}3^{|C^{\prime}_{i}|-2}\\\
&\geq{}-\sum_{i=1}^{\ell}3^{|C^{\circ}_{i}|-2}-\sum_{i=1}^{t}3^{|C^{\bullet}_{i}|-2}+3^{|C_{k}|-2}\\\
&\geq{}-3^{\sum_{i=1}^{\ell}|C^{\circ}_{i}|-2}-3^{\sum_{i=1}^{t}|C^{\bullet}_{i}|-2}+3^{|C_{k}|-2}\\\
&\geq{}-3^{|C_{k}|-3}-3^{|C_{k}|-3}+3^{|C_{k}|-2}=3^{|C_{k}|-3}\geq
0,\end{split}$

where the second inequality follows from Lemma 5.2. This completes the proof.

Let $(U,\rho)$ be a polymatroid. It is well known that, for every vector
$x\in\mathbb{R}^{U}$, $x$ is an extreme point of $\mathbf{B}(\rho)$ if and
only if there exists an ordering $\sigma=(u_{1},u_{2},\dots,u_{|U|})$ of the
elements in $U$ such that

$x(u_{i})=\rho(\\{u_{1},u_{2},\dots,u_{i}\\})-\rho(\\{u_{1},u_{2},\dots,u_{i-1}\\})$

for every integer $i\in[|U|]$ (see [13, 22, 31]). In this case, we say that
_$x$ is generated by $\sigma$_.

To prove that $x^{T}$ is an extreme point of $\mathbf{B}(f)$ for each
elimination tree of $G$, we construct an ordering $\sigma$ on $V$ such that
$x^{T}$ is generated by $\sigma$. To this end, we say the elimination tree $T$
is _compatible with_ an ordering $\sigma=(v_{1},v_{2},\dots,v_{n})$ of the
vertices in $V$ if for every pair of integers $i,j\in[n]$ such that $i\neq j$,
if $v_{i}$ is an ancestor of $v_{j}$ in $T$, then $i<j$. In other words, $T$
is compatible with $\sigma$ if $\sigma$ is a linear extension of $T$ when $T$
is seen as a partially ordered set.

######  Lemma 5.6.

Let $\sigma=(v_{1},v_{2},\dots,v_{n})$ be an ordering of the vertices in $V$.
Let $z$ be an extreme point of $\mathbf{B}(f)$ generated by $\sigma$. In
addition, let $T$ be an elimination tree of $G$ compatible with $\sigma$.
Then, $z=x^{T}$.

######  Proof 5.7.

Let $k$ be an integer in $[n]$. We prove that $z(v_{k})=x^{T}(v_{k})$. Let $C$
be the connected component of $G-\\{v_{1},v_{2},\dots,v_{k-1}\\}$ containing
$v_{k}$. If $v_{k}$ is a leaf of $T$, then $|C|=1$. Thus, we have
$z(v_{k})=x^{T}(v_{k})=0$. Assume that $v_{k}$ is not a leaf of $T$. Notice
that, in this case, $|C|\geq 2$. Let $C_{1},C_{2},\dots,C_{\ell}$ be the
connected components of $G[C]-\\{v_{k}\\}$. Assume that
$C_{1},C_{2},\dots,C_{t}$ are non-trivial, and
$C_{t+1},C_{t+2},\dots,C_{\ell}$ are trivial. For each integer
$i\in[\ell]\setminus[t]$, we assume that $C_{i}=\\{u_{i}\\}$. Let
$c_{1},c_{2},\dots,c_{\ell}$ be the children of $v_{k}$ in $T$. We assume that
$c_{i}\in C_{i}$ for every integer $i\in[\ell]$. Then, for every integer
$i\in[t]$, $T(c_{i})=C_{i}$, which implies that

$\sum_{u\in T(c_{i})}x^{T}(u)=3^{|C_{i}|-2}.$

We have

$z(v_{k})=f(\\{v_{1},v_{2},\dots,v_{k}\\})-f(\\{v_{1},v_{2},\dots,v_{k-1}\\})=3^{|C|-2}-\sum_{i=1}^{t}3^{|C_{i}|-2}.$

Furthermore, since $u_{i}$ is a leaf of $T$ for every integer
$i\in[\ell]\setminus[t]$,

$x^{T}(v_{k})=3^{|C|-2}-\sum_{i=1}^{\ell}\sum_{u\in
T(c_{i})}x^{T}(u)=3^{|C|-2}-\sum_{i=1}^{t}\sum_{u\in
T(c_{i})}x^{T}(u)=3^{|C|-2}-\sum_{i=1}^{t}3^{|C_{i}|-2}.$

Thus, $z(v_{k})=x^{T}(v_{k})$. This completes the proof.

Recall that $\mathcal{E}=\\{x^{T}\in\mathbb{R}^{V}\mid\text{$T$ is an
elimination tree of $G$}\\}$.

######  Lemma 5.8.

The base polytope $\mathbf{B}(f)$ coincides with the convex hull of
$\mathcal{E}$.

######  Proof 5.9.

Let $T$ be an elimination tree of $G$, and let $\sigma$ be an ordering of the
vertices in $V$ such that $T$ is compatible with $\sigma$. Let $z$ be the
extreme point of $\mathbf{B}(f)$ generated by $\sigma$. Then, Lemma 5.6
implies that $z=x^{T}$.

Let $z$ be an extreme point of $\mathbf{B}(f)$. Recall that there exists an
ordering $\sigma=(v_{1},v_{2},\dots,v_{n})$ of the vertices in $V$ such that
$z$ is generated by $\sigma$. Define the elimination tree $T$ as that obtained
by removing the vertices in $V$ according to the ordering $\sigma$. (Namely,
we first remove $v_{1}$, then we remove $v_{2}$, and so on.) Then, $T$ is
compatible with $\sigma$. Thus, Lemma 5.6 implies that $z=x^{T}$.

The following lemma immediately follows from Lemmas 5.1 and 5.8.

######  Lemma 5.10.

The base polytope $\mathbf{B}(f)$ is a realization of the $G$-associahedron. ∎

Thus, we complete the reduction from Combinatorial Shortest Path on Graph
Associahedra to Combinatorial Shortest Path on Polymatroids. Therefore,
Theorem 1.2 follows from Theorem 1.1.

##  6 Conclusion

We prove that the combinatorial shortest path computation is hard on graph
associahedra and base polytopes of polymatroids. This evaporates our hope for
resolving an open problem to obtain a polynomial-time algorithm for finding a
shortest flip sequence between two triangulations of convex polygons and the
rotation distance between two binary trees by generalizing the setting to
graph associahedra. However, that open problem is still open, and we should
pursue another way of attacking it.

## References

  * [1] Oswin Aichholzer, Wolfgang Mulzer, and Alexander Pilz.  Flip distance between triangulations of a simple polygon is NP-complete.  Discret. Comput. Geom., 54(2):368–389, 2015.  doi:10.1007/s00454-015-9709-7.
  * [2] Benjamin Aram Berendsohn.  The diameter of caterpillar associahedra.  In Artur Czumaj and Qin Xin, editors, 18th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2022, June 27-29, 2022, Tórshavn, Faroe Islands, volume 227 of LIPIcs, pages 14:1–14:12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.  doi:10.4230/LIPIcs.SWAT.2022.14.
  * [3] Maike Buchin, Anna Lubiw, Arnaud de Mesmay, and Saul Schleimer.  Computation and reconfiguration in low-dimensional topological spaces (Dagstuhl Seminar 22062).  Dagstuhl Reports, 12(2):17–66, 2022.  doi:10.4230/DagRep.12.2.17.
  * [4] Jean Cardinal, Stefan Langerman, and Pablo Pérez-Lantero.  On the diameter of tree associahedra.  Electron. J. Comb., 25(4):4, 2018.  doi:10.37236/7762.
  * [5] Jean Cardinal, Arturo I. Merino, and Torsten Mütze.  Efficient generation of elimination trees and graph associahedra.  In Joseph (Seffi) Naor and Niv Buchbinder, editors, Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9 - 12, 2022, pages 2128–2140. SIAM, 2022.  doi:10.1137/1.9781611977073.84.
  * [6] Jean Cardinal, Lionel Pournin, and Mario Valencia-Pabon.  Diameter estimates for graph associahedra.  Ann. Comb., 26:873–902, 2022.  doi:10.1007/s00026-022-00598-z.
  * [7] Jean Cardinal, Lionel Pournin, and Mario Valencia-Pabon.  The rotation distance of brooms, 2022.  doi:10.48550/ARXIV.2211.07984.
  * [8] Michael Carr and Satyan L. Devadoss.  Coxeter complexes and graph-associahedra.  Topology and its Applications, 153(12):2155–2168, 2006.  doi:https://doi.org/10.1016/j.topol.2005.08.010.
  * [9] Cesar Ceballos, Francisco Santos, and Günter M. Ziegler.  Many non-equivalent realizations of the associahedron.  Combinatorica, 35(5):513–551, 2015.  doi:10.1007/s00493-014-2959-9.
  * [10] Sean Cleary and Katherine St. John.  Rotation distance is fixed-parameter tractable.  Inf. Process. Lett., 109(16):918–922, 2009.  doi:10.1016/j.ipl.2009.04.023.
  * [11] Sean Cleary and Katherine St. John.  A linear-time approximation algorithm for rotation distance.  J. Graph Algorithms Appl., 14(2):385–390, 2010.  doi:10.7155/jgaa.00212.
  * [12] Satyan L. Devadoss.  A realization of graph associahedra.  Discrete Mathematics, 309(1):271–276, 2009.  doi:10.1016/j.disc.2007.12.092.
  * [13] Jack Edmonds.  Submodular functions, matroids, and certain polyhedra.  In Richard Guy, Haim Hanani, Norbert Sauer, and Johanan Schönheim, editors, Combinatorial Structures and their Applications, pages 69–87. Gordon and Breach, New York, NY, 1970.
  * [14] Uriel Feige and Mohammad Mahdian.  Finding small balanced separators.  In Jon M. Kleinberg, editor, Proceedings of the 38th Annual ACM Symposium on Theory of Computing, Seattle, WA, USA, May 21-23, 2006, pages 375–384. ACM, 2006.  doi:10.1145/1132516.1132573.
  * [15] Alan M. Frieze and Shang-Hua Teng.  On the complexity of computing the diameter of a polytope.  Comput. Complex., 4:207–219, 1994.  doi:10.1007/BF01206636.
  * [16] Satoru Fujishige.  Submodular Functions and Optimization, volume 58 of Annals of Discrete Mathematics.  Elsevier, Amsterdam, The Netherlands, 2nd edition, 2005.
  * [17] Jacob E. Goodman, Joseph O’Rourke, and Csaba D. Tóth, editors.  Handbook of Discrete and Computational Geometry, Third Edition.  CRC Press LLC, 2017.
  * [18] 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.  doi:10.1016/j.tcs.2010.12.005.
  * [19] Volker Kaibel and Marc E. Pfetsch.  Some algorithmic problems in polytope theory.  In Michael Joswig and Nobuki Takayama, editors, Algebra, Geometry, and Software Systems [outcome of a Dagstuhl seminar], pages 23–47. Springer, 2003.  doi:10.1007/978-3-662-05148-1_2.
  * [20] Iyad A. Kanj, Eric Sedgwick, and Ge Xia.  Computing the flip distance between triangulations.  Discret. Comput. Geom., 58(2):313–344, 2017.  doi:10.1007/s00454-017-9867-x.
  * [21] Haohong Li and Ge Xia.  An $\mathcal{O}(3.82^{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.  doi:10.4230/LIPIcs.STACS.2023.44.
  * [22] László Lovász.  Submodular functions and convexity.  In Achim Bachem, Bernhard Korte, and Martin Grötschel, editors, Mathematical Programming – The State of the Art, pages 235–257. Springer Berlin Heidelberg, Berlin, Heidelberg, Germany, 1983.  doi:10.1007/978-3-642-68874-4_10.
  * [23] Anna Lubiw and Vinayak Pathak.  Flip distance between two triangulations of a point set is NP-complete.  Comput. Geom., 49:17–23, 2015.  doi:10.1016/j.comgeo.2014.11.001.
  * [24] Joan M. Lucas.  An improved kernel size for rotation distance in binary trees.  Inf. Process. Lett., 110(12-13):481–484, 2010.  doi:10.1016/j.ipl.2010.04.022.
  * [25] Thibault Manneville and Vincent Pilaud.  Graph properties of graph associahedra.  Seminaire Lotharingien de Combinatoire, 73:B73d, 2015.
  * [26] Alexander Pilz.  Flip distance between triangulations of a planar point set is APX-hard.  Comput. Geom., 47(5):589–604, 2014.  doi:10.1016/j.comgeo.2014.01.001.
  * [27] Alex Postnikov, Victor Reiner, and Lauren Williams.  Faces of generalized permutohedra.  Doc. Math., 13:207–273, 2008.
  * [28] Lionel Pournin.  The diameter of associahedra.  Advances in Mathematics, 259:13–42, 2014.  doi:https://doi.org/10.1016/j.aim.2014.02.035.
  * [29] Lionel Pournin.  The asymptotic diameter of cyclohedra.  Israel Journal of Mathematics, 219(2):609–635, 2017.  doi:10.1007/s11856-017-1492-0.
  * [30] Laura Sanità.  The diameter of the fractional matching polytope and its hardness implications.  In Mikkel Thorup, editor, 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 910–921. IEEE Computer Society, 2018.  doi:10.1109/FOCS.2018.00090.
  * [31] Lloyd S. Shapley.  Cores of convex games.  International Journal of Game Theory, 1:11–26, 1971.  doi:10.1007/BF01753431.
  * [32] Daniel D. Sleator, Robert E. Tarjan, and William P. Thurston.  Rotation distance, triangulations, and hyperbolic geometry.  J. Amer. Math. Soc., 1:647–681, 1988.  doi:10.1090/S0894-0347-1988-0928904-4.
  * [33] Donald M. Topkis.  Adjacency on polymatroids.  Math. Program., 30(2):229–237, 1984.  doi:10.1007/BF02591887.