University of Bergen<EMAIL_ADDRESS>University of Bergen,
<EMAIL_ADDRESS>University of Bergen<EMAIL_ADDRESS>University of Bergen<EMAIL_ADDRESS>Benjamin Bergougnoux,
Svein Høgemo, Jan Arne Telle and Martin Vatshelle [500]Mathematics of
computing Graph algorithms

###### Acknowledgements.

# Recognition of Linear and Star Variants of Leaf Powers is in P

Benjamin Bergougnoux  Svein Høgemo  Jan Arne Telle  Martin Vatshelle

###### Abstract

A $k$-leaf power of a tree $T$ is a graph $G$ whose vertices are the leaves of
$T$ and whose edges connect pairs of leaves whose distance in $T$ is at most
$k$. A graph is a leaf power if it is a $k$-leaf power for some $k$. Over 20
years ago, Nishimura et al. [J. Algorithms, 2002] asked if recognition of leaf
powers was in P. Recently, Lafond [SODA 2022] showed an XP algorithm when
parameterized by $k$, while leaving the main question open. In this paper, we
explore this question from the perspective of two alternative models of leaf
powers, showing that both a linear and a star variant of leaf powers can be
recognized in polynomial-time.

###### keywords:

Leaf powers, Co-threshold tolerance graphs, Interval graphs, Neighborhood
subtree

###### category:

###### keywords:

Leaf power Co-threshold tolerance graphs Interval graphs

##  1 Introduction

Leaf powers were introduced by Nishimura et al. in [23], and have enjoyed a
steady stream of research. Leaf powers are related to the problem of
reconstructing _phylogenetic trees_. For an integer $k$, a graph $G$ is a
$k$-leaf power if there exists a tree $T$ – called a _leaf root_ – with a one-
to-one correspondence between $V(G)$ and the leaves of $T$, such that two
vertices $u$ and $v$ are neighbors in $G$ iff the distance between the two
corresponding leaves in $T$ is at most $k$. $G$ is a leaf powers if it is a
$k$-leaf power for some $k$. The most important open problem in the field is
whether leaf powers can be recognized in polynomial time.

Most of the results on leaf powers have followed two main lines, focusing
either on the distance values $k$ or on the relation of leaf powers to other
graph classes, see e.g. the survey by Calamoneri et al. [7]. For the first
approach, steady research for increasing values of $k$ has shown that $k$-leaf
powers for any $k\leqslant 6$ is recognizable in polytime [4, 5, 8, 11, 12,
23]. Moreover, the recognition of $k$-leaf powers is known to be FPT
parameterized by $k$ and the degeneracy of the graph [13]. Recently Lafond
[19] gave a polynomial time algorithm to recognize $k$-leaf powers for any
constant value of $k$. For the second approach, we can mention that interval
graphs [5] and rooted directed path graphs [3] are leaf powers, and also that
leaf powers have mim-width one [17] and are strongly chordal. Moreover, an
infinite family of strongly chordal graphs that are not leaf powers has been
identified [18]; see also Nevris and Rosenke [22].

To decide if leaf powers are recognizable in polynomial time, it may be better
not to focus on the distance values $k$. Firstly, the specialized algorithms
for $k$-leaf powers for $k\leqslant 6$ do not seem to generalize. Secondly,
the recent XP algorithm of Lafond [19] uses techniques that will not allow
removing $k$ from the exponent. In this paper we therefore take a different
approach, and consider alternative models for leaf powers that do not rely on
a distance bound. In order to make progress towards settling the main
question, we consider fundamental restrictions on the shape of the trees, in
two distinct directions: subdivided caterpillars (linear) and subdivided
stars, in both cases showing polynomial-time recognizability. We use two
models: weighted leaf roots for the linear case and NeS models for the stars.

The first model uses rational edge weights between 0 and 1 in the tree $T$
which allows to fix a bound of 1 for the tree distance. It is not hard to see
that this coincides with the standard definition of leaf powers using an
unweighted tree $T$ and a bound $k$ on distance. Given a solution of the
latter type we simply set all edge weights to $1/k$, while in the other
direction we let $k$ be the least common denominator of all edge weights and
then subdivide each edge a number of times equal to its weight times $k$.

The second model arises by combining the result of Brandstädt et al. that leaf
powers are exactly the fixed tolerance NeST graphs [3, Theorem 4] with the
result of Bibelnieks et al. [1, Theorem 3.3] that these latter graphs are
exactly those that admit what they call a “neighborhood subtree intersection
representation”, that we choose to call a NeS model. NeS models are a
generalization of interval models: by considering intervals of the line as
having a center that stretches uniformly in both directions, we can generalize
the line to a tree embedded in the plane, and the intervals to embedded
subtrees with a center, stretching uniformly in all directions from the
center, along tree edges. Thus a NeS model of a graph $G$ consists of an
embedded tree and one such subtree for each vertex, such that two vertices are
adjacent in $G$ iff their subtrees have non-empty intersection. Precise
definitions are given later. The leaf powers are exactly the graphs having a
NeS model. Some results are much easier to prove using NeS models, to
illustrate this, we show that leaf powers are closed under several operations
such as the addition of a universal vertex (see Lemma 4.4).

We show that fundamental constraints on these models allow polynomial-time
recognition. Using the first model, we restrict to edge-weighted caterpillars,
i.e. trees with a path containing all nodes of degree 2 or more. We call
linear leaf power a graph with such model. Brandstädt et al. [2] considered
leaf roots restricted to caterpillars (see also [6]) in the unweighted
setting, showing that unit interval graphs are exactly the $k$-leaf powers for
some $k$ with a leaf root being an unweighted caterpillar. In the unweighted
setting, linear leaf powers are graphs with a leaf root that is a subdivision
of a caterpillar. We show that linear leaf powers are exactly the _co-
threshold tolerance graphs_ [20], and combined with the algorithm of Golovach
et al. [14] this implies that we can recognize linear leaf powers in
$O(n^{2})$ time. Our proof goes via the equivalent concept of blue-red
interval graphs introduced by [15], see Figure 3.

The recognition of linear leaf powers in polynomial time could have practical
applications for deciding whether the most-likely evolutionary tree associated
with a set of organisms has a linear topology. Answering this question might
find particular relevance inside the field of Tumor phylogenetics where, under
certain model assumptions, linear topologies are considered more likely [9,
25].

For NeS models, we restrict to graphs having a NeS model where the embedding
tree is a star, and show that they can be recognized in polynomial time. Note
that allowing the embedding tree to be a subdivided star will result in the
same class of graphs. Our algorithm uses the fact that the input graph must be
a chordal graph, and for each maximal clique $X$ we check if $G$ admits a star
NeS model where the set of vertices having a subtree containing the central
vertex of the star is $X$. To check this we use a combinatorial
characterization, that we call a “good partition”, of a star NeS model.

##  2 Preliminaries

For positive integer $k$, denote by $[k]$ the set $\\{1,2,\dots,k\\}$. A
partition of a set $S$ is a collection of non-empty disjoint subsets
$B_{1},\dots,B_{t}$ of $S$ – called blocks – such that $S=B_{1}\cup\dots\cup
B_{t}$. Given two partitions $\mathcal{A},\mathcal{B}$ of $S$, we say
$\mathcal{A}\sqsubseteq\mathcal{B}$ if every block of $\mathcal{A}$ is
included in a block of $\mathcal{B}$, i.e. $\sqsubseteq$ is the _refinement_
relation.

Graph. Our graph terminology is standard and we refer to [10]. The vertex set
of a graph $G$ is denoted by $V(G)$ and its edge set by $E(G)$. An edge
between two vertices $x$ and $y$ is denoted by $xy$ or $yx$. The set of
vertices that is adjacent to $x$ is denoted by $N(x)$. A vertex $x$ is
simplicial if $N(x)$ is a clique. Two vertices $x,y$ are true twins if $xy\in
E(G)$ and $N(x)\setminus\\{y\\}=N(y)\setminus\\{x\\}$. Given $X\subseteq
V(G)$, we denote by $G[X]$ the graph induced by $X$. Given a vertex $v\in
V(G)$, we denote the subgraph $G[V(G)\setminus\\{v\\}]$ by $G-v$. We denote by
$\mathsf{CC}(G)$ the partition of $G$ into its connected components. Given a
tree $T$ and an edge-weight function $\mathsf{w}:E(T)\to\mathbb{Q}$, the
distance between two vertices $x$ and $y$ is denoted by $d_{T}(x,y)$ is
$\sum_{e\in E(P)}\mathsf{w}(e)$ with $P$ is the unique path between $x$ and
$y$.

Leaf power. In the Introduction we have already given the standard definition
of leaf powers and leaf roots, and also we argued the equivalence with the
following. Given a graph $G$, a leaf root of $G$ is a pair $(T,\mathsf{w})$ of
a tree $T$ and a rational-valued weight function $\mathsf{w}:E(T)\to[0,1]$
such that the vertices of $G$ are the leaves of $T$ and for every $u,v\in
V(G)$, $u$ and $v$ are adjacent iff $d_{T}(u,v)\leqslant 1$. Moreover, if $T$
is a caterpillar we call $(T,\mathsf{w})$ a _linear leaf root_. A graph is a
_leaf power_ if it admits a leaf root and it is a linear leaf power if it
admits a linear leaf root. Since we manipulate both the graphs and the trees
representing them, the vertices of trees will be called _nodes_ to avoid
confusion.

Interval graphs. A graph $G$ is an _interval graph_ if there exists a set of
intervals in $\mathbb{Q}$, $\mathcal{I}=(I_{v})_{v\in V(G)}$, such that for
every pair of vertices $u,v\in V(G)$, the intervals $I_{v}$ and $I_{u}$
intersect iff $uv\in E(G)$. We call $(I_{v})_{v\in V(G)}$ an _interval model_
of $G$. For an interval $I=[\ell,r]$, we define the midpoint of $I$ as
$(\ell+r)/2$ and its length as $r-\ell$.

Clique tree. For a chordal graph $G$, a clique tree $CT$ of $G$ is a tree
whose vertices are the maximal cliques of $V(G)$ and for every vertex $v\in
V(G)$, the set of maximal cliques of $G$ containing $v$ induces a subtree of
$CT$. Figure 4 gives an example of clique tree. Every chordal graph admits
$O(n)$ maximal cliques and given a graph $G$, in time $O(n+m)$ we can
construct a clique tree of $G$ or confirm that $G$ is not chordal [16, 24].
When a clique tree is a path, we call it a clique path. We denote by
$(K_{1},\dots,K_{k})$ the clique path whose vertices are $K_{1},\dots,K_{k}$
and where $K_{i}$ is adjacent to $K_{i+1}$ for every $i\in[k-1]$.

##  3 Linear leaf powers

In this section we show that linear leaf powers are exactly the _co-threshold
tolerance graphs_ (co-TT graphs). Combined with the algorithm in [14], this
implies that we can recognize linear leaf powers in $O(n^{2})$ time.

Co-TT graphs were defined by Monma, Trotter and Reed in [20]; we will not
define them here as we do not use this characterization. Rather, we work with
the equivalent class of _blue-red interval graphs_ [15, Proposition 3.3].

######  Definition 3.1 (Blue-red interval graph).

A graph $G$ is a _blue-red interval_ graph if there exists a bipartition
$(B,R)$ of $V(G)$ and an interval model $\mathcal{I}=(I_{v})_{v\in V(G)}$
(with $(B,R,\mathcal{I})$ called a blue-red interval model) such that
$E(G)=\\{b_{1}b_{2}\,:\,b_{1},b_{2}\in B\text{ and }I_{b_{1}}\cap
I_{b_{2}}\neq\varnothing\\}\cup\\{rb\,:\,r\in R,b\in B\text{ and
}I_{r}\subseteq I_{b}\\}.$

The red vertices induce an independent set, $(I_{b})_{b\in B}$ is an interval
model of $G[B]$, and we have a blue-red edge for each red interval contained
in a blue interval. The following fact can be easily deduced from Figure 1.

######  Fact 1.

Consider two intervals $I_{1},I_{2}$ with lengths $\ell_{1},\ell_{2}$ and
midpoints $m_{1},m_{2}$ respectively. We have $I_{1}\cap I_{2}\neq\varnothing$
iff $|m_{1}-m_{2}|\leqslant\frac{\ell_{1}+\ell_{2}}{2}$. Moreover, we have
$I_{2}\subseteq I_{1}$ iff
$|m_{1}-m_{2}|\leqslant\frac{\ell_{1}-\ell_{2}}{2}$.

Figure 1: Example of two intervals overlapping and one interval containing
another one.

To prove that linear leaf powers are exactly blue-red interval graphs, we use
a similar construction as the one used in [2, Theorem 6] to prove that every
interval graph is a leaf power, but in our setting, we have to deal with red
vertices and this complicates things quite a bit.

######  Theorem 3.2 ($\star$).

$G$ is a blue-red interval graph iff $G$ is a linear leaf power.

######  Proof 3.3.

($\Rightarrow$) Let $G$ be a blue-red interval graph with blue-red interval
model $(B,R,(I_{v})_{v\in V(G)})$. We assume w.l.o.g. that $G$ is connected as
otherwise we can obtain a leaf root of $G$ from leaf roots of its connected
components by creating a new node adjacent to an internal node of each leaf
root via edges of weight 1. For every $v\in V(G)$, we denote by $\ell(v)$ and
$m(v)$ the length and the midpoint of the interval $I_{v}$. We suppose
w.l.o.g. that, for every $v\in V(G)$, we have $0<\ell(v)\leqslant 1$ as we can
always divide the endpoints of all intervals by
$\mathsf{max}\\{\ell(v)\,:\,v\in V(G)\\}$ and add some $\epsilon>0$ to the
right endpoints of the intervals of length 0. We fix an ordering on $V(G)$,
$\\{v_{1},\dots,v_{n}\\}$, such that $m(v_{i})\leqslant m(v_{j})$ for every
$i<j$.

We define $T$ a caterpillar and its edges
$f_{1},\dots,f_{n},e_{1},\dots,e_{n-1}$ as depicted in Figure 2. Let
$\mathsf{w}:E(T)\to[0,1]$ such that for every $i\in[n-1]$ we have
$\mathsf{w}(e_{i})=m(v_{i+1})-m(v_{i})$ and for every $i\in[n]$ the weight of
$f_{i}$ is $\frac{1-\ell(v_{i})}{2}$ if $v_{i}\in B$ and
$\frac{1+\ell(v_{i})}{2}$ if $v_{i}\in R$. Since we assume that $G$ is
connected and the length of the intervals are at most 1, for every
$i\in[n-1]$, we have $\mathsf{w}(e_{i})=m(v_{i+1})-m(v_{i})\leqslant 1$ so the
weights are well-defined.

Figure 2: The linear branch-decomposition used to prove that every blue-red
interval graph is a linear leaf power. Observe that the weight of an edge
$e_{i}$ can be 0 if $I_{v_{i}}$ and $I_{v_{i-1}}$ have the same midpoint, in
that case, $e_{i}$ can be contracted.

We claim that $(T,\mathsf{w})$ is a linear leaf root of $G$. Let $i,j\in[n]$
such that $i<j$. We have to prove that $v_{i}v_{j}\in E(G)$ iff
$d_{T}(v_{i},v_{j})\leqslant 1$. The edges of the path between $v_{i}$ and
$v_{j}$ in $T$ are $f_{i},e_{i},e_{i+1},\dots,e_{j-1},f_{j}$. By construction,
we have

$\mathsf{w}(e_{i})+\dots+\mathsf{w}(e_{j-1})=m_{i+1}-m_{i}+m_{i+2}-m_{i+1}+\dots+m_{j-1}-m_{j-2}+m_{j}-m_{j-1}=m_{j}-m_{i}.$

Hence $d_{T}(v_{i},v_{j})=\mathsf{w}(f_{i})+|m_{j}-m_{i}|+\mathsf{w}(f_{j})$.
If $v_{i}$ and $v_{j}$ are red vertices, then
$\mathsf{w}(f_{i}),\mathsf{w}(f_{j})>\frac{1}{2}$ because we suppose that
$\ell(x)>0$ for every vertex $x$. Thus, $d_{T}(v_{i},v_{j})>1$ for every pair
of red vertices $(v_{i},v_{j})$. So at least one vertex among $v_{i},v_{j}$ is
blue. Suppose w.l.o.g. that $v_{i}$ is blue. As
$d_{T}(v_{i},v_{j})=\mathsf{w}(f_{i})+|m_{j}-m_{i}|+\mathsf{w}(f_{j})$, we
deduce that

$d_{T}(v_{i},v_{j})=\begin{cases}1+|m(v_{i})-m(v_{j})|-\left(\frac{\ell(v_{i})+\ell(v_{j})}{2}\right)&\text{
if }v_{j}\in B\\\
1+|m(v_{i})-m(u_{i})|-\left(\frac{\ell(v_{i})-\ell(v_{j})}{2}\right)&\text{ if
}v_{j}\in R.\end{cases}$ (1)

If $v_{j}\in B$ then by Fact 1, we have $I_{v_{i}}\cap
I_{v_{j}}\neq\varnothing$ iff
$|m(v_{i})-m(v_{j})|\leqslant\frac{\ell(v_{i})+\ell(v_{j})}{2}$. We conclude
that $v_{i}v_{j}\in E(G)$ iff
$d_{T}(v_{i},v_{j})=|m(v_{i})-m(v_{j})|-\left(\frac{\ell(v_{i})+\ell(v_{j})}{2}\right)+1\leqslant
1.$ On the other hand, if $v_{j}\in R$ then $I_{v_{j}}\subseteq I_{v_{i}}$ iff
$|m(v_{i})-m(v_{j})|\leqslant\frac{\ell(v_{i})-\ell(v_{j})}{2}$. We conclude
that $v_{i}v_{j}\in E(G)$ iff
$d_{T}(v_{i},v_{j})=|m(v_{i})-m(v_{j})|-\left(\frac{\ell(v_{i})-\ell(v_{j})}{2}\right)+1\leqslant
1.$ Hence, $(T,\mathsf{w})$ is a linear leaf root of $G$. This proves that
every blue-red interval graph is a linear leaf power.

($\Leftarrow$) Let $G$ be a linear leaf power and $(T,\mathsf{w})$ a linear
leaf root of $G$. Let $(u_{1},\dots,u_{t})$ be the path induced by the
internal vertices of $T$. We suppose w.l.o.g. that $G$ does not contain
isolated vertices as we can easily deal with such vertices by associating each
of them with an interval that does not intersect the other intervals.
Consequently, for every leaf $a$ of $T$ adjacent to some $u_{i}$, we have
$d_{T}(a,u_{i})\leqslant 1$. For every vertex $v\in V(G)$ whose neighbor in
$T$ is $u_{i}$, we associate $v$ with an interval $I_{v}$ and a color such
that the midpoint of $I_{v}$ is $m(v)=d_{T}(u_{1},u_{i})$ and

  * •

if $\mathsf{w}(u_{i}v)\leqslant\frac{1}{2}$, the length of $I_{v}$ is
$\ell(v)=1-2\mathsf{w}(u_{i}v)$ and the color of $v$ is blue,

  * •

otherwise ($\frac{1}{2}<\mathsf{w}(u_{i}v)\leqslant 1$), the length of $I_{v}$
is $\ell(v)=2\mathsf{w}(u_{i}v)-1$ and the color of $v$ is red.

Let $B,R\subseteq V(G)$ be the sets of blue and red vertices respectively.
Observe that the red vertices induce an independent set since their distance
to the inner path is strictly more than $1/2$. By construction, we have the
following equation for every vertex $v$ whose neighbor in $T$ is $u_{i}$

$w(u_{i}v)=\begin{cases}\frac{1-\ell(v)}{2}&\text{if }v\in B,\\\
\frac{1+\ell(v)}{2}&\text{if }v\in R.\end{cases}$ (2)

Moreover, from the definition of the midpoint’s, we deduce that for every
$v_{i},v_{j}\in V(G)$ whose neighbors in $T$ are respectively $u_{i}$ and
$u_{j}$, we have

$d_{T}(v_{i},v_{j})=|m(v_{i})-m(v_{j})|+w(u_{i}v_{i})+w(u_{j}v_{j}).$ (3)

From Equations 2 and 3, we deduce that Equation 1 holds also for this
direction for every $v_{i}\in B$ and $v_{j}\in V(G)$. By Fact 1 and with
symmetrical arguments to the ones of the previous direction, we conclude that
$(B,R,(I_{v})_{v\in V(G)})$ is a blue-red interval model of $G$.

Figure 3: A split graph $G$ with a blue-red interval model of $G$ and a linear
leaf root of $G$ obtained from the blue-red interval model by using the
construction described in Theorem 3.2. Note the midpoint of each interval has
been marked, to better understand where each vertex is placed in $T$. Weights
on edges is calculated as explained in the proof of Theorem 3.2 and note every
edge has a weight that is a multiple of $\frac{1}{24}$ because the length of
$I_{3}$ is 12.

##  4 Star NeS model

In this section, we first present an alternative definition of leaf powers
through the notion of NeS models. We then show that we can recognize in
polynomial time graphs with a star NeS model: a NeS model whose embedding tree
is a star (considering subdivided stars instead of stars does not make a
difference).

For each tree $T$, we consider a corresponding tree $\mathcal{T}$ embedded in
the Euclidean plane so that each edge of $T$ corresponds to a line segment of
$\mathcal{T}$, these lines segments can intersect one another only at their
endpoints, and the vertices of $T$ correspond (one-to-one) to the endpoints of
the lines. Each line segment of $\mathcal{T}$ has a positive Euclidean length.
These embedded trees allow us to consider $\mathcal{T}$ as the infinite set of
points on the line segments of $\mathcal{T}$. The notion of tree embedding
used here is consistent with that found in [26]. The line segments of
$\mathcal{T}$ and their endpoints are called respectively the edges and the
nodes of $\mathcal{T}$. The distance between two points $x,y$ of $\mathcal{T}$
denoted by $d_{\mathcal{T}}(x,y)$ is the length of the unique path in
$\mathcal{T}$ between $x$ and $y$ (the distance between two vertices of $T$
and their corresponding endpoints in $\mathcal{T}$ are the same).

######  Definition 4.1 (Neighborhood subtree, NeS-model).

Let $\mathcal{T}$ be an embedding tree. For some point $c\in\mathcal{T}$ and
non-negative rational $w$, we define the neighborhood subtree with center $c$
and radius $w$ as the set of points
$\\{p\in\mathcal{T}\,:\,d_{\mathcal{T}}(p,c)\leqslant w\\}$. A NeS model
$(\mathcal{T},(T_{v})_{v\in V(G)})$ of a graph $G$ is a pair of an embedding
tree $\mathcal{T}$ and a collection of neigbhorhood subtrees of $\mathcal{T}$
associated with each vertex of $G$ such that for every $u,v\in V(G)$, we have
$uv\in E(G)$ iff $T_{u}\cap T_{v}\neq\varnothing$.

######  Theorem 4.2.

A graph is a leaf power iff it admits a NeS model.

######  Proof 4.3.

Brandstädt et al. showed that leaf powers correspond to the graph class fixed
tolerance NeST graph [3, Theorem 4]. Bidelnieks and Dearing showed that $G$ is
a fixed tolerance NeST graph iff $G$ has a NeS model [1, Theorem 3.3].

Figure 4: A graph with a clique tree and NeS model. The dots are centers of
$T_{a}$ and $T_{b}$.

See Figure 4 for a NeS model. Observe that every interval graph has a NeS
model where the embedding tree is a single edge. Moreover, if a graph $G$
admits a NeS model $(\mathcal{T},(T_{v})_{v\in V(G)})$, then for every
embedding path $\mathcal{L}$ of $\mathcal{T}$,
$(\mathcal{L},(T_{v}\cap\mathcal{L})_{v\in X})$ is an interval model of $G[X]$
with $X$ the set of vertices $v$ such that $T_{v}$ intersects $\mathcal{L}$.
As illustrated by the proofs of the following two lemmata, some results are
easier to prove with NeS models than with other characterizations.

We use the following operation on NeS models several times in the following
proofs:

  * •

Given a NeS model $(\mathcal{T},(T_{v})_{v\in V(G)})$ of a graph $G$ and $x\in
V(G)$, if the center $c_{x}$ of $T_{x}$ is not an endpoint, we turn it into
one by splitting the line containing $c_{x}$. We add a new line $L$ with
endpoint $c_{x}$ that is sufficiently long so that $L$ contains a point $p$
that is not in any neighborhood subtree. We replace the center of $T_{x}$ by
$p$ and increase the radius of $T_{v}$ by $d_{\mathcal{T}}(p,c_{x})$.

We call this operation _isolating_ $T_{x}$ in $(\mathcal{T},(T_{v})_{v\in
V(G)})$. Observe that after this operation, $(\mathcal{T},(T_{v})_{v\in
V(G)})$ will remain a NeS model of $G$ since the intersection relations
between $T_{x}$ and the other neighborhood subtrees do not change. Moreover,
after this operation, $T_{x}$ is the only neighborhood subtree in
$(T_{v})_{v\in V(G)})$ that contains the center of $T_{x}$.

######  Lemma 4.4.

For a graph $G$ and $u\in V(G)$ such that either (1) $u$ is universal, or (2)
$u$ has degree 1, or (3) $N(u)$ is a minimal separator in $G-u$, or (4) $N(u)$
is a maximal clique in $G-u$. Then $G$ is a leaf power iff $G-u$ is a leaf
power.

######  Proof 4.5.

The forward implication is trivial as being a leaf power is a hereditary
property. For the backward implication, we assume we have a NeS model
$(\mathcal{T},(T_{v})_{v\in V(G-u)})$ of $G-u$, and in each case we show how
to obtain a NeS model for $G$:

  * •

$u$ is universal, we simply create $T_{u}$ a neighborhood subtree with an
arbitrary center and a radius sufficiently large so that $T_{u}$ intersects
all the other neighborhood subtrees.

  * •

$u$ has degree $1$ with $x$ as neighbor. We isolate $T_{x}$ in
$(\mathcal{T},(T_{v})_{v\in V(G-u)})$. Then, we set $T_{u}=\\{c_{x}\\}$ where
$c_{x}$ is the (new) center of $T_{x}$.

  * •

$N(u)$ is a maximal clique in $G-u$. Then $T=\cap_{v\in N(u)}T_{v}$ is not
empty and the only neighborhood subtrees intersecting $T$ are those associated
with the vertices in $N(u)$. We set $T_{u}=\\{c_{u}\\}$ for some arbitrary
point $c_{u}\in T$.

  * •

$N(u)$ is a minimal separator in $G-u$. Let $T=\cap_{v\in N(u)}T_{v}$. Since
$T$ is the intersection of neighborhood subtrees, by [1, Lemma 2.1], $T$ is a
neighborhood subtree and has a center $c_{T}$. We add a line $L$ to
$\mathcal{T}$ with endpoint $c_{T}$. Let $c_{u}$ be the point on $L\cap T$
such that $d_{\mathcal{T}}(c_{T},c_{u})$ is maximum. As $N(u)$ is a minimal
separator, the only neighborhood subtrees containing $T$ are those associated
with the vertices in $N(u)$. By construction, we deduce that the only
neighborhood subtrees containing $c_{u}$ are those associated with the
vertices in $N(u)$. We set $T_{u}=\\{c_{u}\\}$.

It is not hard to see that in each case, $(\mathcal{T},(T_{v})_{v\in V(G)})$
is a NeS model of $G$.

######  Lemma 4.6.

Let $G$ be a graph and $u\in V(G$ a cut vertex. Then $G$ is a leaf power iff
for every component $C$ of $G-u$, $G[V(C)\cup\\{u\\}]$ is a leaf power.

######  Proof 4.7.

As with Lemma 4.4, the forward implication is trivial. For the backward
implication, let $C_{1},\dots,C_{k}$ be the components of $G-u$, and for every
$1\leqslant i\leqslant k$ we let $C^{+}_{i}=G[V(C_{i})\cup\\{u\\}]$. By
assumption, every $C^{+}_{i}$ is a leaf power and there exists a NeS model
$(\mathcal{T}^{i},(T^{i}_{v})_{v\in V(C^{+}_{i})})$ of $C^{+}_{i}$. For each
$1\leqslant i\leqslant k$, we do the following, we isolate $T_{u}^{i}$ in
$(\mathcal{T}_{i},(T^{i}_{v})_{v\in V(C^{+}_{i})})$ and we make the new center
$c_{u}^{i}$ of $T_{u}^{i}$ an endpoint by subdividing the new line containing
$c_{u}^{i}$. Then, we multiply the length of every line of $\mathcal{T}_{i}$
and the radius of every $(T^{i}_{v})_{v\in V(C^{+}_{i})}$ by
$\frac{1}{r_{u}^{i}}$ where $r_{u}^{i}$ is the new radius of $T_{u}^{i}$.
After these operations, for every $1\leqslant i\leqslant k$, the radius of
$T_{u}^{i}$ is 1 and $T_{u}^{i}$ is the only neighborhood subtree in
$(T_{v})_{v\in V(C_{i}^{+})})$ that contains the center of $T_{u}^{i}$.

We make a new NeS model $(\mathcal{T},(T_{v})_{v\in V(G)})$ where
$\mathcal{T}$ is obtained from the union of
$\mathcal{T}_{1},\dots,\mathcal{T}_{k}$ by identifying the centers (which are
endpoints) of the neighborhood subtrees $T_{u}^{1},\dots,T_{u}^{k}$ as a
unique point $c_{u}$ We define $T_{u}$ the neighborhood subtree with center
$c_{u}$ and radius 1. Finally, for every $v\in V(G-u)$, we define
$T_{v}=T_{v}^{i}$ with $i\in[k]$ such that $v\in V(C_{i})$. It is
straightforward to check that $(\mathcal{T},(T_{v})_{v\in V(G)})$ is a NeS
model of $G$.

We now give the algorithm for recognizing graphs having a star NeS model. Our
result is based on the purely combinatorial definition of good partition, and
we show that a graph admits a star NeS model iff it admits a good partition.
Given a good partition, we compute a star NeS model in polynomial time.
Finally, we prove that our Algorithm 1 in polynomial time constructs a good
partition of the input graph or confirms that it does not admit one.

Consider a star NeS model $(\mathcal{T},(T_{v})_{v\in V(G)})$ of a graph $G$.
Observe that $\mathcal{T}$ is the union of line segments
$L_{1},\dots,L_{\beta}$ with a common endpoint $c$ that is the center of
$\mathcal{T}$. Let $X$ be the set of vertices whose neighborhood subtrees
contain $c$. For each $i\in[\beta]$, we let $B_{i}$ be the set of all vertices
in $V(G)\setminus X$ whose neighborhood subtrees are subsets of $L_{i}$. The
family $\mathcal{B}=\\{B_{i}\,:\,i\in[\beta]\\}$ must then constitute a
partition of $V(G)\setminus X$. We will show in Theorem 4.11 that the pair
$(X,\mathcal{B})$ has the properties of a good partition.

######  Fact 2.

Let $G$, $(\mathcal{T},(T_{v})_{v\in V(G)})$ and $\mathcal{B}$ be as defined
above. We then have:

  * •

There is no edge between $B_{i}$ and $B_{j}$ for $i\neq j$ and thus
$\mathsf{CC}(G-X)\sqsubseteq\mathcal{B}$.

  * •

For every $i\in[\beta]$ the NeS model $(L_{i},(T_{v}\cap L_{i})_{v\in
B_{i}\cup X})$ is an interval model of $G[X\cup B_{i}]$.

  * •

For each $x\in X$ the neighborhood subtree $T_{x}$ is the union of the $\beta$
intervals $L_{1}\cap T_{x},\dots,L_{\beta}\cap T_{x}$ and there exist positive
rationals $\ell_{x}$ and $h_{x}$ with $\ell_{x}\leqslant h_{x}$ such that one
interval among these intervals has length $h_{x}$ and the other $\beta-1$
intervals have length $\ell_{x}$.

  * •

If $\ell_{x}=h_{x}$, then the center of $T_{x}$ is $c$.

######  Claim 3.

If $G$ has a star NeS model, it has a one, $(\mathcal{T},(T_{v})_{v\in
V(G)})$, where vertices whose neighborhood subtrees contain the center of
$\mathcal{T}$ is a maximal clique.

Let $(\mathcal{T},(T_{v})_{v\in V(G)})$ be the star NeS model of a graph $G$
with $c$ the center of $\mathcal{T}$. Suppose that the set $X$ of vertices $x$
such that $c\in T_{x}$ is not a maximal clique. We deduce that there exists at
least one maximal clique $Y$ containing $X$. For every such clique $Y$,
$\cap_{y\in Y}T_{y}$ does not contain $c$ since $X\subset Y$. We take a
maximal clique $Y$ such that $X\subset Y$ and
$\mathsf{min}\\{d_{T}(c,p)\,:\,p\in\cap_{y\in Y}T_{y}\\}$ is minimum. Let $L$
be the line segment of $\mathcal{T}$ containing $\cap_{y\in Y}T_{y}$. By Fact
2, the neighborhood subtrees of the vertices in $Y\setminus X$ are intervals
of $L$. We modify the NeS model by stretching the neighborhood subtrees of the
vertices in $Y\setminus X$ so that they admit $c$ as an endpoint. After this
operation, these subtrees remain intervals of $L$ and consequently, they still
are neighborhood subtrees. Moreover, the choice of $Y$ implies that the only
neighborhood subtrees that were intersecting the interval between $c$ and
$\cap_{y\in Y}T_{y}$ are those associated with the vertices of $Y$. Thus,
after this operation, we obtain a star NeS model where the set of vertices $x$
such that $c\in T_{x}$ is now the maximal clique $Y$.

Claim 3 follows since we can always stretch some intervals to make $X$ a
maximal clique. So far we have described a good partition as it arises from a
star NeS model. Now we introduce the properties of a good partition that will
allow to abstract away from geometrical aspects while still being equivalent,
i.e. so that a graph has a good partition $(X,\mathcal{B})$ iff it has a star
NeS model. The first property is $\mathsf{CC}(G-X)\sqsubseteq\mathcal{B}$ and
the second is that for every $B\in\mathcal{B}$ the graph $G[X\cup B]$ is an
interval graph having a model where the intervals of $X$ contain the last
point used in the interval representation.

######  Definition 4.8 ($X$-interval graph).

Let $X$ be a maximal clique of $G$. We say that $G$ is an $X$-interval graph
if $G$ admits a clique path $(K_{1},\dots,K_{k},X)$.

The third property is the existence of an elimination order for the vertices
of $X$ based on the lengths $\ell_{x}$ in the last item of Fact 2, namely the
permutation $(x_{1},\dots,x_{t})$ of $X$ such that
$\ell_{x_{1}}\leqslant\ell_{x_{2}}\leqslant\dots\leqslant\ell_{x_{t}}$. This
permutation has the property that for any $i\in[t]$, among the vertices
$x_{i},x_{i+1},...,x_{t}$ the vertex $x_{i}$ must have the minimal
neighborhood in at least $\beta-1$ of the blocks of $\mathcal{B}$; we say that
$x_{i}$ is _removable_ from $\\{x_{i},\dots,x_{t}\\}$ for $\mathcal{B}$.

######  Definition 4.9 (Removable vertex).

Let $X\subseteq V(G)$, $Y\subseteq X$ and let $\mathcal{B}$ be a partition of
$V(G)\setminus X$. Given a block $B$ of $\mathcal{B}$ and $x\in Y$, we say
$N(x)$ is minimal in $B$ for $Y$ if $N(x)\cap B\subseteq N(y)$ for every $y\in
Y$. We say that a vertex $x\in Y$ is removable from $Y$ for $\mathcal{B}$ if
$N(x)$ is minimal in at least $\lvert\mathcal{B}\rvert-1$ blocks of
$\mathcal{B}$ for $Y$.

######  Definition 4.10 (Good partition).

A good partition of a graph $G$ is a pair $(X,\mathcal{B})$ where $X$ is a
maximal clique of $G$ and $\mathcal{B}$ a partition of $V(G)\setminus X$
satisfying:

  1. 1.

$\mathsf{CC}(G-X)\sqsubseteq\mathcal{B}$, i.e. every $C\in\mathsf{CC}(G-X)$ is
contained in a block of $\mathcal{B}$.

  2. 2.

For each block $B\in\mathcal{B}$, $G[X\cup B]$ is an $X$-interval graph.

  3. 3.

There exists an elimination order $(x_{1},\dots,x_{t})$ on $X$ such that for
every $i\in[t]$, $x_{i}$ is removable from $\\{x_{i},\dots,x_{t}\\}$ for
$\mathcal{B}$.

$X$ is the central clique of $(X,\mathcal{B})$ and $(x_{1},\dots,x_{t})$ a
good permutation of $(X,\mathcal{B})$.

######  Theorem 4.11.

A graph $G$ admits a good partition iff it admits a star NeS model. Moreover,
given the former we can compute the latter in polynomial time.

######  Proof 4.12.

($\Leftarrow$) Let $G$ be a graph with a star NeS model
$(\mathcal{T},(T_{v})_{v\in V(G)})$. Let $X$ be the set of vertices $x$ such
that $T_{x}$ contains the center $c$ of the star $\mathcal{T}$. By Claim 3, we
can assume that $X$ is a maximal clique. As $\mathcal{T}$ is a star,
$\mathcal{T}$ is an union of line segments $L_{1},\dots,L_{\beta}$ with one
common endpoint that is $c$. Let $\mathcal{B}=\\{B_{1},\dots,B_{\beta}\\}$
such that, for every $i\in[\beta]$, $B_{i}$ is the set of vertices $v\in
V(G)\setminus X$ such that $T_{v}$ intersects $L_{i}$. We claim that
$(X,\mathcal{B})$ is a good partition of $G$. Fact 2 implies that Property 1
and Property 2 are satisfied. For every $x\in X$, let $\ell_{x}$ be the
rational defined in Fact 2. Take a permutation $(x_{1},\dots,x_{t})$ of $X$
such that
$\ell_{x_{1}}\leqslant\ell_{x_{2}}\leqslant\dots\leqslant\ell_{x_{t}}$. Let
$f(i)\in[\beta]$ such that the center of $x_{i}$ lies in $L_{f(i)}$. From Fact
2, we have $\lvert T_{x_{i}}\cap L_{j}\rvert=\ell_{x_{i}}$ for every $j\neq
f(i)$. Hence, for every $j\neq f(i)$ the interval $T_{x_{i}}\cap L_{j}$ are
contained in the neighborhood subtree $T_{y}$ for every
$y\in\\{x_{i},\dots,x_{t}\\}$. Consequently, $N(x_{i})$ is minimal in $B_{j}$
for $\\{x_{i},\dots,x_{t}\\}$ for every $j\neq f(i)$. We conclude that
$(x_{1},\dots,x_{t})$ is a good permutation of $(X,\mathcal{B})$, i.e.
Property 3 is satisfied.

($\Rightarrow$) Let $(X,\mathcal{B})$ be a good partition of a graph $G$ with
$\mathcal{B}=\\{B_{1},\dots,B_{\beta}\\}$ and $(x_{1},\dots,x_{t})$ be a good
permutation of $X$. For every $i\in[t]$, we define
$X_{i}=\\{x_{i},\dots,x_{t}\\}$. Since $x_{i}$ is removable from $X_{i}$,
there exists an integer $f(i)\in[\beta]$ such that $N(x_{i})$ is minimal for
$X_{i}$ in every block of $\mathcal{B}$ different from $B_{f(i)}$ (note that
$f(i)$ is not necessarily unique, as $x_{i}$ could be minimal in every block
of $\mathcal{B}$ for $X_{i}$).

Take $\mathcal{T}$, the embedding of a star with center $c$ that is the union
of $\beta$ line segments $L_{1},\dots,L_{\beta}$ of length $2t+1$ whose
intersection is $\\{c\\}$. We start by constructing the neighborhood subtree
of the vertices in $X$. For doing so, we associate each $x_{i}\in X$ and each
segment $L_{j}$ with a rational $\ell(x_{i},L_{j})$ and define $T_{x_{i}}$ as
the union of over $j\in[\beta]$ of the points on $L_{j}$ at distance at most
$\ell(x_{i},L_{j})$ from $c$ .

For every $i\in[t]$ and $j\in[\beta]$ such that $j\neq f(i)$, we define
$\ell(x_{i},L_{j})=i$. We define $\ell(x_{t},L_{f(t)})=t$ and for every $i$
from $t-1$ to $1$ we define $\ell(x_{i},L_{f(i)})$ as follows:

  * •

If $N(x_{i})$ is minimal in $B_{f(i)}$ for $X_{i}$ then we define
$\ell(x_{i},L_{f(i)})=i$.

  * •

If $N(x_{j})\cap B_{f(i)}\subset N(x_{i})$ for every $x_{j}\in X_{i}$, then we
define $\ell(x_{i},L_{f(i)})=1+\mathsf{max}\\{\ell(y,L_{f(i)})\,:\,y\in
X_{i+1}\\}$.

  * •

Otherwise, we take $x_{\mathsf{min}}$ and $x_{\mathsf{max}}\in X_{i+1}$ such
that

$N(x_{\mathsf{min}})\cap B_{f(i)}\subseteq N(x_{i})\cap B_{f(i)}\subseteq
N(x_{\mathsf{max}})\cap B_{f(i)}$

and $N(x_{\mathsf{min}})\cap B_{f(i)}$ is maximal and $N(x_{\mathsf{max}})\cap
B_{f(i)}$ is minimal. We define
$\ell(x_{i},L_{f(i)})=(\ell(x^{\mathsf{min}},L_{f(i)})+\ell(x^{\mathsf{max}},L_{f(i)}))/2.$
Observe that the vertices $x_{\mathsf{min}}$ and $x_{\mathsf{max}}$ exist
because $G[X\cup B_{f(i)}]$ is an $X$-interval graph and thus the
neighborhoods of the vertices in $X$ in $B_{f(i)}$ are pairwise comparable for
the inclusion.

By construction, we deduce the following properties on the lengths
$\ell(x_{i},L_{j})$.

######  Claim 4.

The following conditions hold for every $j\in[\beta]$:

  1. 1.

For every $i\in[t]$, we have $\ell(x_{i},L_{j})\geqslant i$.

  2. 2.

For every $x,y\in X$, if $N(x)\cap B_{j}\subset N(y)$ then
$\ell(x,L_{j})<\ell(y,L_{j})$.

We prove by induction on $i$ from $t$ to $1$ that Condition (1) holds for
$x_{i}$ and that Condition (2) holds for every $x,y\in X_{i}$. That is
obviously the case when $i=t$. Let $i\in[t-1]$ and suppose that Condition (1)
holds for every $x_{i+1},\dots,x_{t}$ and Condition (2) holds for every
$x,y\in X_{i+1}$. Let $j\in[\beta]$ such that $B_{j}\neq B_{f(i)}$. By
construction, we have $\ell(x_{i},L_{j})=i$ so Condition (1) holds for $x_{i}$
and $B_{j}$. Moreover, we have $N(x_{i})\setminus B_{x_{i}}\subseteq N(y)$ for
every $y\in X_{i}$. As $B_{j}\neq B_{f(i)}$, it follows that $N(x_{i})\cap
B_{j}\subseteq N(y)$ for every $y\in X_{i}$. The induction hypothesis implies
that $\ell(y,L_{j})\geqslant i+1$ for every $y\in X_{i}$. Hence,
$\ell(x_{i},L_{j})<\ell(y,L_{j})$ for every $y\in X_{i}$ and Condition (2)
holds for $X_{i}$ and every $B_{j}\neq B_{f(i)}$.

It remains to prove that both Conditions holds for $B_{f(i)}$. We define
$\ell(x_{i},L_{f(i)})$ either to $i$, $a+1$ or $(b+c)/2$ where $a,b$ and $c$
belong to $\\{\ell(y,L_{f(i)})\,:\,y\in X_{i+1}\\}$. The induction assumption
implies that $\ell(y,L_{f(i)})\geqslant i+1$ for every $y\in X_{i+1}$. Thus
$a,b$ and $c$ greater than or equal to $i+1$. We deduce that
$\ell(x_{i},L_{f(i)})\geqslant i$. This proves that Condition (1) holds for
$x_{i}$.

If $N(x_{i})$ is minimal in $B_{f(i)}$ for $X_{i}$, then
$\ell(x_{i},L_{j})<\ell(y,L_{j})$ for every $y\in X_{i}$ and Condition (2) is
satisfied. Suppose that $N(x_{i})$ is maximal in $B_{f(i)}$ for $X_{i}$, i.e.
$N(y)\cap B_{f(i)}\subseteq N(x_{i})$ for every $y\in X_{i}$. In this case, we
set $\ell(x_{i},L_{f(i)})$ is define as
$1+\mathsf{max}\\{\ell(y,L_{f(i)})\,:\,y\in X_{i+1}\\}$. Thus, we have
$\ell(x_{i},L_{f(i)})>\ell(y,L_{f(i)})$ for every $y\in X_{i+1}$ and Condition
(2) holds for $\leqslant_{B_{f(i)}}$.

Finally, assume that $N(x_{i})$ is neither minimal nor maximal in $B_{f(i)}$
for $X_{i}$. If $x^{\mathsf{max}}=x^{\mathsf{min}}$, then we have
$\ell(x_{i},L_{f(i)})=\ell(x^{\mathsf{max}},L_{f(i)})$ and also $N(x_{i})\cap
B_{f(i)}=N(x^{\mathsf{min}})\cap B_{f(i)}$. We deduce that Condition (2) holds
for every $x,y\in X_{i}$ because by induction hypothesis we have for every
$x,y\in X_{i+1}$ and $x^{\mathsf{min}}\in X_{i+1}$.

Now, assume that $x^{\mathsf{min}}\neq x^{\mathsf{max}}$. The way we choose
$x^{\mathsf{min}}$ and $x^{\mathsf{max}}$ implies that

$N(x^{\mathsf{min}})\cap B_{f(i)}\subset N(x_{i})\cap B_{f(i)}\subset
N(x^{\mathsf{max}})\cap B_{f(i)}.$

As $N(x^{\mathsf{min}})\cap B_{f(i)}\subset N(x^{\mathsf{max}})\cap B_{f(i)}$,
by induction hypothesis, we deduce that
$\ell(x^{\mathsf{min}},L_{f(i)})<\ell(x^{\mathsf{max}},L_{f(i)})$ and thus we
have

$\ell(x^{\mathsf{min}},L_{f(i)})<\ell(x_{i},L_{f(i)})<\ell(x^{\mathsf{max}},L_{f(i)})$

So Condition (2) holds for every
$x,y\in\\{x_{i},x^{\mathsf{min}},x^{\mathsf{max}}\\}$.

Let $y\in X_{i+1}$ such that $N(x_{i})\cap B_{f(i)}\subseteq N(y)$. The
minimality of $N(x^{\mathsf{max}})\cap B_{f(i)}$ implies that
$N(x^{\mathsf{max}})\cap B_{f(i)}\subseteq N(y)$. By induction hypothesis, we
have $\ell(x^{\mathsf{max}},L_{f(i)})\leqslant\ell(y,L_{f(i)})$. Thus, for
every $y\in X_{i+1}$ such that $N(x_{i})\cap B_{f(i)}\subseteq N(y)$, we have
$\ell(x_{i},L_{f(i)})<\ell(y,L_{f(i)})$.

Symmetrically, the maximality of $x^{\mathsf{min}}$ implies that for every
$y\in X_{i+1}$ such that $N(y)\cap B_{f(i)}\subseteq N(x_{i})$, we have
$\ell(y,L_{f(i)})<\ell(x_{i},L_{f(i)})$. We conclude that Condition (2) holds
for every $x,y\in X_{i}$. By induction, we conclude that Condition (1) holds
for every $i\in[t]$ and Condition (2) holds for every $x,y\in X$. This
concludes the proof of Claim 4.

Observe that each $T_{x_{i}}$ is a neighborhood subtree as by construction and
Condition (1) of Claim 4 the lengths $\ell(x_{i},L_{j})$ satisfy the last item
of Fact 2. See Figure 5 for an illustration of this neighborhood subtree.

Figure 5: Illustration of the neighborhood subtree $T_{x_{i}}$ where the
number $\beta$ of edges of the star NeS model is 4.

It remains to construct the neighborhood subtrees of the vertices in
$V(G)\setminus X$. Let us explain how we do it for the vertices in $B_{j}$ for
some $j\in[\beta]$. For every $b\in B_{j}$, we define $T_{b}$ as an interval
on the line segment $L_{j}$. As $(X,\mathcal{B})$ is a good partition,
$G[X\cup B_{j}]$ admits a clique path $(X,K_{1},\dots,K_{k})$. Clique path
properties implies that $X\supseteq K_{1}\cap X\supseteq\dots\supseteq
K_{k}\cap X$. For every $i\in[k]$, $x\in X\setminus K_{i}$ and $y\in X\cap
K_{i}$, we have $N(x)\cap B_{j}\subset N(y)$ and thus
$\ell(x,L_{j})<\ell(y,L_{j})$ thanks to Condition (2) of Claim 4. As
$\ell(x,L_{j})$ corresponds to the length of the interval $T_{x}\cap L_{j}$
for every $x\in X$, we conclude that there exist $p_{1},\dots,p_{k}$ points on
$L_{j}$ such that

  * •

for every $i\in[k]$, $K_{i}\cap X$ is exactly the set of vertices $x$ in $X$
such that $p_{i}\in T_{x}$ and

  * •

we have
$0<d_{\mathcal{T}}(p_{1},c)<d_{\mathcal{T}}(p_{2},c)<\dots<d_{\mathcal{T}}(p_{k},c)$.

For every $b\in B_{j}$ such that $b$ is contained in every clique $K_{i}$ for
$i$ between $s$ and $t$, we define $T_{b}$ as the interval of $L_{j}$ between
$p_{s}$ and $p_{t}$.

By construction, $(\mathcal{T},(T_{v})_{v\in V(G)})$ fulfill every property of
Fact 2. We deduce that $(\mathcal{T},(T_{v})_{v\in V(G)})$ is a NeS model of
$G$. Obviously, the construction of $(\mathcal{T},(T_{v})_{v\in V(G)})$ can be
done in polynomial time.

It is easy to see that every graph that admits a star NeS model has a clique-
tree that is a subdivided star. The converse is not true. In fact, for every
graph $G$ with a clique tree that is a subdivided star with center $X$, the
pair $(X,\mathsf{CC}(G-X))$ satisfies Properties 1 and 2 of Definition 4.10
but Property 3 might not be satisfied. See for example the graph in Figure 4
and note that the pair $(\\{a,b,c\\},\mathsf{CC}(G-\\{a,b,c\\}))$ does not
satisfy Property 3, as after removing the vertex $c$ neither $a$ nor $b$ is
removable from $\\{a,b\\}$.

We now describe Algorithm 1 that decides whether a graph $G$ admits a good
partition. Clearly $G$ must be chordal, so we start by checking this. A
chordal graph has $O(n)$ maximal cliques, and for each maximal clique $X$ we
try to construct a good partition $(X,\mathcal{A})$ of $G$. We start with
$\mathcal{A}\leftarrow\mathsf{CC}(G-X)$ and note that $(X,\mathcal{A})$
trivially satisfies Property 1 of Definition 4.10. Moreover, if $G$ admits a
good partition with central clique $X$, then $(X,\mathcal{A})$ must satisfy
Property 2 of Definition 4.10, and we check this in Line 1. Then, Algorithm 1
iteratively in a while loop tries to construct a good permutation
$(w_{1},\dots,w_{\lvert X\rvert})$ of $X$, while possibly merging some blocks
of $\mathcal{A}$ along the way so that it satisfies Property 3, or discover
that there is no good partition with central clique $X$.

For doing so, at every iteration of the while loop, Algorithm 1 searches for a
vertex $w$ in $W$ (the set of unprocessed vertices) such that
$\mathsf{notmin}(w,W,\mathcal{A})$ – the union of the blocks of $\mathcal{A}$
where $N(w)$ is not minimal for $W$ (see Definition 4.13) – induces an
$X$-interval graph with $X$. If such a vertex $w$ exists, then Algorithm 1
sets $w_{r}$ to $w$, increments $r$ and merges the blocks of $\mathcal{A}$
contained in $\mathsf{notmin}(w_{r},W,\mathcal{A})$ (Line 1) to make $w_{r}$
removable in $\mathcal{A}$ for $W$. Otherwise, when no such vertex $w$ exists,
Algorithm 1 stops the while loop (Line 1) and tries another candidate for $X$.
For the graph in Figure 4, with $X=\\{a,b,c\\}$ the first iteration of the
while loop will succeed and set $w_{1}=c$, but in the second iteration neither
$a$ nor $b$ satisfy the condition of Line 1.

At the start of an iteration of the while loop, the algorithm has already
choosen the vertices $w_{1},w_{2},...,w_{r-1}$ and
$W=X\setminus\\{w_{1},\dots,w_{r-1}\\}$. For every $i\in[r-1]$, $w_{i}$ is
removable from $X\setminus\\{w_{1},\dots,w_{i-1}\\}$ for $\mathcal{A}$.
According to Definition 4.9 the next vertex $w_{r}$ to be removed should have
$N(w_{r})$ non-minimal for $W$ in at most one block of the good partition we
want to construct. However, the neighborhood $N(w_{r})$ may be non-minimal for
$W$ in several blocks of the current partition $\mathcal{A}$, since these
blocks may be (unions of) separate components of $G\setminus X$ that should
live on the same line segment of a star NeS model and thus actually be a
single block which together with $X$ induces an $X$-interval graph. An example
of this merging is given in Figure 6. The following definition captures, for
each $w\in W$, the union of the blocks of $\mathcal{A}$ where $N(w)$ is not
minimal for $W$.

######  Definition 4.13 ($\mathsf{notmin}$).

For $W\subseteq X$, $x\in W$ and partition $\mathcal{A}$ of $V(G)\setminus X$,
we denote by $\mathsf{notmin}(x,W,\mathcal{A})$ the union of the blocks
$A\in\mathcal{A}$ where $N(x)$ is not minimal in $A$ for $W$.

Input: A graph $G$.

Output: A good partition of $G$ or “no”.

1 Check if $G$ is chordal and if so, compute its set of maximal cliques
$\mathcal{X}$, otherwise return no;

2 for  _every $X\in\mathcal{X}$_ do

3 if  _there exists $C\in\mathsf{CC}(G-X)$ such that $G[X\cup C]$ is not an
$X$-interval graph_ then continue;

4 $\mathcal{A}\leftarrow\mathsf{CC}(G-X)$, $W\leftarrow X$ and $r\leftarrow
1$;

5 while  _$W\neq\varnothing$_ do

6 if  _there exists $w\in W$ such that
$G[X\cup\mathsf{notmin}(w_{r},W,\mathcal{A})]$ is an $X$-interval graph_ then
$w_{r}\leftarrow w$;

7 else break;

8 Replace the blocks of $\mathcal{A}$ contained in
$\mathsf{notmin}(w_{r},W,\mathcal{A})$ by
$\mathsf{notmin}(w_{r},W,\mathcal{A})$;

9 $W\leftarrow W\setminus\\{w_{r}\\}$ and $r\leftarrow r+1$;

10

11 end while

12 if  _$W=\varnothing$_ then return $(X,\mathcal{A})$;

13

14 end for

15return no;

Algorithm 1

As we already argued, when Algorithm 1 starts a while loop, $(X,\mathcal{A})$
satisfies Properties 1 and 2, and it is not hard to argue that in each
iteration, for every $i\in[r-1]$, $w_{i}$ is removable from
$X\setminus\\{w_{1},\dots,w_{i-1}\\}$ for $\mathcal{A}$. Hence, when
$W=\varnothing$, then $(w_{1},\dots,w_{\lvert X\rvert})$ is a good permutation
of $(X,\mathcal{A})$ and Property 3 is satisfied.

######  Lemma 4.14.

If Algorithm 1 returns $(X,\mathcal{B})$, then $(X,\mathcal{B})$ is a good
partition.

######  Proof 4.15.

Assume that Algorithm 1 returns a pair $(X,\mathcal{B})$. We show that
$(X,\mathcal{B})$ satisfies Definition 4.10. As the algorithm starts with
$\mathcal{A}=\mathsf{CC}(G-X)$ and only merge blocks, Property 1 holds. Line 1
guarantees that every block of $\mathsf{CC}(G-X)$ induces with $X$ an
$X$-interval graph. Moreover, when merging blocks, Line 1 checks that the
merged block induces with $X$ an $X$-interval graph. Thus Property 2 holds.

Observe that at every step of the while loop, we have
$\mathcal{A}\sqsubseteq\mathcal{B}$ since we only merge blocks of
$\mathcal{A}$ and $\mathcal{B}$ is the last value of $\mathcal{A}$. We show
that $(w_{1},\dots,w_{t})$ is a good permutation of $(X,\mathcal{B})$ where,
for each $i\in[t]$, $w_{i}$ is the vertex chosen by the algorithm at the
$i$-th iteration. Let $i\in[t]$. At the start of the $i$-th iteration of the
while loop, the value of $W$ is $X_{i}=\\{w_{i},\dots,w_{t}\\}$. During this
iteration, we merge the blocks of $\mathcal{A}$ contained in
$\mathsf{notmin}(w_{i},X_{i},\mathcal{A})$. Consequently, after the merging,
there exists a block $A_{w_{i}}$ of $\mathcal{A}$ such that $N(w_{i})$ is
minimum for $X_{i}$ in every block of $\mathcal{A}$ different from
$A_{w_{i}}$. As $\mathcal{A}\sqsubseteq\mathcal{B}$, there exists a block
$B_{w_{i}}$ of $\mathcal{B}$ containing $A_{w_{i}}$. We deduce that,
$N(w_{i})$ is minimal for $X_{i}$ in every block of $\mathcal{B}$ different
from $B_{w_{i}}$, i.e. $w_{i}$ is removable from $X_{i}$ for $\mathcal{B}$.
Thus, $(w_{1},\dots,w_{t})$ is a good permutation of $(X,\mathcal{B})$ and we
conclude that $(X,\mathcal{B})$ is a good partition of $G$.

To prove the opposite direction, namely that if $G$ has a good partition
$(X,\mathcal{B})$ associated with a good permutation $(x_{1},\dots,x_{t})$,
then Algorithm 1 finds a good partition, we need two lemmata. The easy case is
when Algorithm 1 chooses consecutively $w_{1}=x_{1},\dots,w_{t}=x_{t}$, and we
can use Lemma 4.16 to prove that it will not return no. However, Algorithm 1
does not have this permutation as input and at some iteration with
$w_{1}=x_{1},\dots,w_{r-1}=x_{r-1}$, the algorithm might stop to follow the
permutation $(x_{1},\dots,x_{t})$ and choose a vertex $w_{r}=x_{i}$ with $r<i$
because $x_{r}$ may not be the only vertex satisfying the condition of Line 1.
In Lemma 4.18 we show that choosing $w_{r}=x_{i}$ is then not a mistake as it
implies the existence of another good partition and another good permutation
that starts with $(x_{1},\dots,x_{r-1},w_{r}=x_{i})$. See Figure 6 for an
example of a very simple graph with several good permutations leading to quite
distinct star NeS models.

Figure 6: A graph $G$ and two star NeS models. The dots are the centers of the
subtrees. $X=\\{x,y,z\\}$ is a maximal clique with four components in $G-X$.
The left NeS model corresponds to permutations $(y,x,z)$ or $(y,z,x)$ and the
right to permutation $(x,y,z)$. If Algorithm 1 chooses $w_{1}=x$, then the
components $\\{b\\}$ and $\\{d\\}$ will be merged in Line 1. There is a third
star NeS model, corresponding to permutation $(z,y,x)$, similar to the one on
the right. The last two permutations of $X$ are not good permutations.

We need some definitions. Given permutation $P=(x_{1},\dots,x_{\ell})$ of a
subset of $X$ and $i\in[\ell]$, define $\mathcal{A}_{0}^{P}=\mathsf{CC}(G-X)$
and $\mathcal{A}_{i}^{P}$ the partition of $V(G)\setminus X$ obtained from
$\mathcal{A}_{i-1}^{P}$ by merging the blocks contained in
$\mathsf{notmin}(x_{i},X\setminus\\{x_{1},\dots,x_{i-1}\\},\mathcal{A}_{i-1}^{P})$.
Observe that when Algorithm 1 treats $X$ and we have
$w_{1}=x_{1},\dots,w_{\ell}=x_{\ell}$, then the values of $\mathcal{A}$ are
successively $\mathcal{A}_{0}^{P},\dots,\mathcal{A}_{\ell}^{P}$. The following
lemma proves that if there exists a good permutation $P=(x_{1},\dots,x_{t})$
and at some iteration we have $w_{1}=x_{1},\dots,w_{r-1}=x_{r-1}$, then the
vertex $x_{r}$ satisfies the condition of Line 1 and Algorithm 1 does not
return no during this iteration. Thus, as long as Algorithm 1 follows a good
permutation, it will not return no.

######  Lemma 4.16.

Let $G$ be a graph with good partition $(X,\mathcal{B})$ and
$P=(x_{1},\dots,x_{t})$ be a good permutation of $(X,\mathcal{B})$. For every
$i\in[t]$, we have $\mathcal{A}^{P}_{i}\sqsubseteq\mathcal{B}$ and the graph
$G[X\cup\mathsf{notmin}(x_{i},\\{x_{i},\dots,x_{t}\\},\mathcal{A}^{P}_{i-1})]$
is an $X$-interval graph.

######  Proof 4.17.

For every $i\in[t]$, we denote $\\{x_{i},\dots,x_{t}\\}$ by $X_{i}$. We start
by proving by induction that, for every $i\in[t]$, we have
$\mathcal{A}^{P}_{i}\sqsubseteq\mathcal{B}$. This is true for
$\mathcal{A}^{P}_{0}=\mathsf{CC}(G-X)$ by Property 1 of Definition 4.10. Let
$i\in[t]$ and suppose that $\mathcal{A}^{P}_{i-1}\sqsubseteq\mathcal{B}$.
Every block of $\mathcal{A}^{P}_{i}$ different from
$\mathsf{notmin}(x_{i},X_{i},\mathcal{A}^{P}_{i-1})$ is a block of
$\mathcal{A}^{P}_{i-1}$ and is included in a block of $\mathcal{B}$ by the
induction hypothesis. As $x_{i}$ is removable from $X_{i}$ for $\mathcal{B}$,
there exists $B_{x_{i}}\in\mathcal{B}$ such that $N(x_{i})$ is minimal for
$X_{i}$ in every block of $\mathcal{B}$ different from $B_{x_{i}}$. Since
$\mathcal{A}^{P}_{i-1}\sqsubseteq\mathcal{B}$, for every block
$\widehat{A}\in\mathcal{A}^{P}_{i-1}$ such that $N(x_{i})$ is not minimal in
$\widehat{A}$ for $X_{i}$, we have $\widehat{A}\subseteq B_{x_{i}}$. As the
union of these blocks $\widehat{A}$’s is
$\mathsf{notmin}(x_{i},X_{i},\mathcal{A}^{P}_{i-1})$, we deduce that
$\mathsf{notmin}(x_{i},X_{i},\mathcal{A}^{P}_{i-1})\subseteq B_{x_{i}}$.
Hence, every block of $\mathcal{A}^{P}_{i}$ is included in a block of
$\mathcal{B}$, thus by induction $\mathcal{A}^{P}_{i}\sqsubseteq\mathcal{B}$
for every $i\in[t]$.

For every $i\in[t]$, we have proved that
$\mathsf{notmin}(x_{i},X_{i},\mathcal{A}^{P}_{i-1})\subseteq B_{x_{i}}$. From
Property 2 of Definition 4.10, $G[X\cup B_{x_{i}}]$ is an $X$-interval graph.
We conclude that $G[X\cup\mathsf{notmin}(x_{i},X_{i},\mathcal{A}^{P}_{i-1})]$
is also an $X$-interval graph.

######  Lemma 4.18.

Let $P=(x_{1},\dots,x_{t})$ be a good permutation of $X$ and $i\in[t]$. For
every $w\in\\{x_{i},\dots,x_{t}\\}$ such that
$G[X\cup\mathsf{notmin}(w,\\{x_{i},\dots,x_{t}\\},\mathcal{A}_{i-1}^{P})]$ is
an $X$-interval graph, there exists a good permutation of $X$ starting with
$(x_{1},\dots,x_{i-1},w)$.

######  Proof 4.19.

This lemma relies on the following relation that will be applied to vertex
subsets corresponding to unions of connected components of $G-X$.

######  Definition 4.20.

For every $A\subseteq V(G)\setminus X$, we define
$X\text{-}\mathsf{max}_{\cap}(A)=N(A)\cap X$ and
$X\text{-}\mathsf{min}_{\cap}(A)=\cap_{a\in A}N(a)\cap X$. Given
$A_{1},A_{2}\subseteq V(G)\setminus X$, we say that $A_{1}\leqslant_{X}A_{2}$
if $X\text{-}\mathsf{max}_{\cap}(A_{1})\subseteq
X\text{-}\mathsf{min}_{\cap}(A_{2})$.

As an example of the use of this, note that in Figure 6, we have
$\\{b\\}\leqslant_{\\{x,y,z\\}}\\{d\\}$ and in the rightmost star NeS model we
see this ordering reflected by $d$ being placed closer to the center of the
star than $b$.

For every $A\subseteq V(G)\setminus X$, we have
$X\text{-}\mathsf{min}_{\cap}(A)\subseteq X\text{-}\mathsf{max}_{\cap}(A)$ and
thus $\leqslant_{X}$ is transitive. The following claim reveals the connection
between Definition 4.20 and Property 2 of Definition 4.10.

######  Claim 5.

Let $P=(x_{1},\dots,x_{t})$ be a good permutation of $X$ and
$\ell\in\\{0,\dots,t\\}$. For all distinct blocks
$A,A^{\star}\in\mathcal{A}^{P}_{\ell}$, if $G[X\cup A\cup A^{\star}]$ is an
$X$-interval graph, then $A$ and $A^{\star}$ are comparable for
$\leqslant_{X}$.

We prove this claim by induction on $\ell$. By definition, we have
$\mathcal{A}_{0}^{P}=\mathsf{CC}(G-X)$. Let $C,C^{\star}$ be two distinct
components of $G-X$ such that $G[X\cup C\cup C^{\star}]$ is an $X$-interval
graph. Let $(K_{1},\dots,K_{k},X)$ be a clique path of $G[X\cup C\cup
C^{\star}]$. Since $C$ and $C^{\star}$ are distinct connected components, for
every $j\in[k]$, $K_{j}$ is either a maximal clique of $G[X\cup C]$ or
$G[X\cup C^{\star}]$. Assume w.l.o.g. that $K_{1}$ is a maximal clique of
$G[X\cup C]$. Moreover, there exists $j\in[k-1]$ such that
$X,K_{1},K_{2},\dots,K_{j}$ are all the maximal cliques of $G[X\cup C]$ and
$X,K_{j+1},\dots,K_{k}$ are all the maximal cliques of $G[X\cup C^{\star}]$.
Since $(K_{1},\dots,K_{k},X)$ is a clique path, we have $K_{1}\cap
X\subseteq\dots\subseteq K_{k}\cap X\subseteq X$. From Definition 4.20, we
deduce that $X\text{-}\mathsf{max}_{\cap}(C)=K_{j}\cap X$ and
$X\text{-}\mathsf{min}_{\cap}(C^{\star})=K_{j+1}\cap X$. As $K_{j}\cap
X\subseteq K_{j+1}\cap X$, we have $X\text{-}\mathsf{max}_{\cap}(C)\subseteq
X\text{-}\mathsf{min}_{\cap}(C^{\star})$ and thus $C\leqslant_{X}C^{\star}$
and the claim holds for $\mathcal{A}_{0}^{P}$.

Let $\ell\in[t]$ and suppose that the claim holds for
$\mathcal{A}_{\ell-1}^{P}$. In the rest of this proof, we use the shorthand
$\mathsf{notmin}(x_{\ell})$ to denote
$\mathsf{notmin}(x_{\ell},\\{x_{\ell},\dots,x_{t}\\},\mathcal{A}_{\ell-1}^{P})$.
We obtain $\mathcal{A}_{\ell}^{P}$ from $\mathcal{A}_{\ell-1}^{P}$ by merging
the blocks of $\mathcal{A}_{\ell-1}^{P}$ contained in
$\mathsf{notmin}(x_{\ell})$. So every block of $\mathcal{A}_{\ell}^{P}$
different from $\mathsf{notmin}(x_{\ell})$ is also a block of
$\mathcal{A}_{\ell-1}^{P}$. By assumption, the claim holds for every pair of
distinct blocks of
$\mathcal{A}_{\ell}^{P}\setminus\\{\mathsf{notmin}(x_{\ell})\\}$. To prove
that it holds for $\mathcal{A}_{\ell}^{P}$, it is enough to prove that it
holds for every pair $(A,\mathsf{notmin}(x_{\ell}))$ with
$A\neq\mathsf{notmin}(x_{\ell})$.

Let $A\in\mathcal{A}_{\ell}^{P}$ such that $A\neq\mathsf{notmin}(x_{\ell})$
and $G[X\cup A\cup\mathsf{notmin}(x_{\ell})]$ is an $X$-interval graph. We
need to prove that $A\leqslant_{X}\mathsf{notmin}(x_{\ell})$ or
$\mathsf{notmin}(x_{\ell})\leqslant_{X}A$. Observe that
$\mathsf{notmin}(x_{\ell})$ is a union of blocks $A_{1},\dots,A_{k}$ of
$\mathcal{A}_{\ell-1}^{P}$. As $G[X\cup A\cup\mathsf{notmin}(x_{\ell})]$ is an
$X$-interval graph, also for any two blocks $B,C$ out of $A,A_{1},\dots,A_{k}$
the graph $G[X\cup B\cup C]$ is an $X$-interval graph, and thus by induction
hypothesis, we deduce that every pair of blocks among $A,A_{1},\dots,A_{k}$ is
comparable for $\leqslant_{X}$. Suppose w.l.o.g. that
$A_{1}\leqslant_{X}\dots\leqslant_{X}A_{k}$.

Assume towards a contradiction that there exists $j\in[k-1]$ such that
$A_{j}\leqslant_{X}A\leqslant_{X}A_{j+1}$. By Definition 4.13, we have

$X\text{-}\mathsf{max}_{\cap}(A_{j})\subseteq
X\text{-}\mathsf{min}_{\cap}(A)\subseteq
X\text{-}\mathsf{max}_{\cap}(A)\subseteq
X\text{-}\mathsf{min}_{\cap}(A_{j+1}).$

Since $N(w)$ is not minimal in $A_{j}$ for $X_{\ell}$, we have $N(w)\cap
A_{j}\neq\varnothing$ and thus $w\in X\text{-}\mathsf{max}_{\cap}(A_{j})$. We
deduce that $w$ belongs to $X\text{-}\mathsf{min}_{\cap}(A)$ and
$X\text{-}\mathsf{min}_{\cap}(A_{j+1})$ and thus $A,A_{j+1}\subseteq N(w)$. As
$N(w)$ is not minimal in $A_{j+1}$ and $A_{j+1}\subseteq N(w)$, we deduce that
there exists $y\in X_{\ell}$ such that $A_{j+1}\not\subseteq N(y)$ which means
that $y\notin X\text{-}\mathsf{min}_{\cap}(A_{j+1})$. Since
$X\text{-}\mathsf{max}_{\cap}(A)\subseteq
X\text{-}\mathsf{min}_{\cap}(A_{j+1})$, we have $y\notin
X\text{-}\mathsf{max}_{\cap}(A)$. Hence, $A\subseteq N(w)$ and $N(y)\cap
A=\varnothing$. We conclude that $N(w)$ is not minimal in $A$ for $X_{\ell}$,
a contradiction with $A\neq\mathsf{notmin}(x_{\ell})$ because $N(w)$ is
minimal for $X_{\ell}$ in every block of $\mathcal{A}_{\ell}^{P}$ different
from $\mathsf{notmin}(x_{\ell})$.

It follows that $A\leqslant_{X}A_{1}$ or $A_{k}\leqslant_{X}A$. Since
$\mathsf{notmin}(x_{\ell})=A_{1}\cup\dots\cup A_{k}$, we deduce that
$A\leqslant_{X}\mathsf{notmin}(x_{\ell})$ or
$\mathsf{notmin}(x_{\ell})\leqslant_{X}A$, that is the claim holds for
$\mathcal{A}_{\ell}^{P}$. By induction, we conclude that the claim is true for
every $\ell\in\\{0,\dots,t\\}$.

######  Claim 6.

Let $X\subseteq V(G)$ and $\mathcal{A}$ a partition of $V(G)\setminus X$ such
that $\mathsf{CC}(G-X)\sqsubseteq\mathcal{A}$. For any
$A_{1},\dots,A_{k}\in\mathcal{A}$ that are pairwise comparable for
$\leqslant_{X}$, if for each $j\in[k]$ $G[X\cup A_{j}]$ is an $X$-interval
graph, then $G[X\cup A_{1}\cup\dots\cup A_{k}]$ is an $X$-interval graph.

Let $A_{1},\dots,A_{k}$ be $k$ blocks of $\mathcal{A}$ such that
$A_{1}\leqslant_{X}A_{2}\leqslant_{X}\dots\leqslant_{X}A_{k}$. Assume that
$G[X\cup A_{j}]$ is an $X$-interval graph for each $j\in[k]$.

Since $G[X\cup A_{j}]$ is an $X$-interval graph for every $j\in[k]$, $G[X\cup
A_{j}]$ admits a clique path $(K_{1}^{j},\dots,K_{f(i)}^{j},X)$, where $f(j)$
is the number of maximal cliques minus one in $G[X\cup A_{j}]$. For every
$j\in[k]$, we have $K_{1}^{j}\cap X\subseteq K_{2}^{j}\cap
X\subseteq\dots\subseteq K_{f(j)}^{j}\cap X$. Moreover, by definition, we have
$X\text{-}\mathsf{min}_{\cap}(A_{i})=K_{1}^{j}$ and
$X\text{-}\mathsf{max}_{\cap}(A_{i})=K_{f(j)}^{j}$. For every $j\in[k-1]$,
since $A_{j}\leqslant_{X}A_{j+1}$, we have
$X\text{-}\mathsf{max}_{\cap}(A_{j})\subseteq
X\text{-}\mathsf{min}_{\cap}(A_{j+1})$, that is $K_{f(j)}^{j}\cap X\subseteq
K_{1}^{j+1}\cap X$. Because $\mathsf{CC}(G-X)\sqsubseteq\mathcal{A}$, every
maximal clique of $G[X\cup A_{1}\cup\dots\cup A_{k}]$ different from $X$ is a
maximal clique of a unique $G[X\cup A_{j}]$. We conclude that
$(K_{1}^{1},\dots,K_{f(1)}^{1},\dots,K_{1}^{k},\dots,K_{f(k)}^{k},X)$ is a
clique path of $G[X\cup A_{1}\cup\dots\cup A_{k}]$.

For every $\ell\in[t]$, we denote by $X_{\ell}$ the set
$\\{x_{\ell},\dots,x_{t}\\}$. Let $w\in X_{i}$ such that
$G[X\cup\mathsf{notmin}(w,X_{i},\mathcal{A}_{i-1}^{P})]$ is an $X$-interval
graph. Let $(X,\mathcal{B})$ be a good partition of $G$ such that
$(x_{1},\dots,x_{t})$ is a good permutation of $(X,\mathcal{B})$. If $w=x_{p}$
is removable from $\mathcal{B}$ for $X_{i}$, then
$(x_{1},\dots,x_{i-1},w,x_{i},\dots,x_{p-1},x_{p+1},\dots,x_{t})$ is a good
permutation of $(X,\mathcal{B})$ and we are done. In particular, $w$ is
removable from $\mathcal{B}$ if
$\lvert\mathsf{notmin}(w,X_{i},\mathcal{A}_{i-1}^{P})\rvert\leqslant 1$. In
the following, we assume that
$\lvert\mathsf{notmin}(w,X_{i},\mathcal{A}_{i-1}^{P})\rvert\geqslant 2$.

We construct a good partition $(X,\mathcal{B}_{\mathsf{new}})$ that admits
good permutation starting with $(x_{1},\dots,x_{i-1},w)$. Let
$A_{1},\dots,A_{k}\in\mathcal{A}_{i-1}^{P}$ such that
$\mathsf{notmin}(w,X_{i},\mathcal{A}_{i-1}^{P})=A_{1}\cup A_{2}\cup\dots\cup
A_{k}$. As $G[X\cup\mathsf{notmin}(w,X_{i},\mathcal{A}_{i-1}^{P})]$ is an
$X$-interval graph, by Claim 5, the blocks $A_{1},\dots,A_{k}$ are pairwise
comparable for $\leqslant_{X}$. Suppose w.l.o.g. that
$A_{1}\leqslant_{X}\dots\leqslant_{X}A_{k}$. In Figure 6 with
$\mathsf{notmin}(x,\\{x,y,z\\},\\{\\{a\\},\\{b\\},\\{c\\},\\{d\\}\\})=\\{b\\}\cup\\{d\\}$
we have $A_{1}=\\{b\\}$ and $A_{2}=\\{d\\}$.

By Lemma 4.16, we have $\mathcal{A}_{i-1}^{P}\sqsubseteq\mathcal{B}$. Thus,
there exists a block $B_{1}$ of $\mathcal{B}$ containing $A_{1}$ and $B_{1}$
is a union of blocks of $\mathcal{A}_{i-1}^{P}$. Let $B_{1}^{\mathsf{max}}$ be
the union of all the blocks $A$ of $\mathcal{A}_{i-1}^{P}$ included in $B_{1}$
such that $A$ is not contained in
$\mathsf{notmin}(w,X_{i},\mathcal{A}_{i-1}^{P})$ and $A_{1}\leqslant_{X}A$.
Note that for every $A\in B_{1}^{\mathsf{max}}$, we have $A_{k}\leqslant_{X}A$
because otherwise we have $A_{1}\leqslant_{X}A\leqslant_{X}A_{k}$ and that
implies $A\subseteq\mathsf{notmin}(w,X_{i},\mathcal{A}_{i-1}^{P})$ (see the
arguments used in the proof of Claim 5).

######  Claim 7.

We can assume that $B_{1}^{\mathsf{max}}$ is empty.

Suppose that $B_{1}^{\mathsf{max}}\neq\varnothing$. Let
$B_{1}^{\star}=B_{1}\setminus B_{1}^{\mathsf{max}}$ and $\mathcal{B}^{\star}$
the partition obtained from $\mathcal{B}$ by replacing the block $B_{1}$ with
the blocks $B_{1}^{\mathsf{max}}$ and $B_{1}^{\star}$. As
$B_{1}^{\mathsf{max}}$ is a union of blocks of $\mathcal{A}_{i-1}^{P}$ and
$\mathcal{A}_{i-1}^{P}\sqsubseteq\mathcal{B}$, by construction, we have
$\mathcal{A}_{i-1}^{P}\sqsubseteq\mathcal{B}^{\star}$. We claim that
$(X,\mathcal{B}^{\star})$ is a good partition that admits
$(x_{1},\dots,x_{t})$ as a good permutation, this is sufficient to prove the
claim.

As $\mathsf{CC}(G-X)\sqsubseteq\mathcal{A}_{i-1}^{P}$, by definition we have
$\mathsf{CC}(G-X)\sqsubseteq\mathcal{B}^{\star}$. So Property 1 of Definition
4.10 is satisfied. As $B_{1}^{\star}$ and $B_{1}^{\mathsf{max}}$ are subsets
of $B_{1}$, we deduce that $G[X\cup B_{1}^{\star}]$ and $G[X\cup
B_{1}^{\mathsf{max}}]$ are both $X$-interval graphs. Thus, Property 2 is
satisfied.

It remains to prove that $(x_{1},\dots,x_{t})$ is a good permutation of
$(X,\mathcal{B}^{\star})$. First, observe that for every $j\in[i-1]$, by
definition, $x_{j}$ is removable from $X_{j}$ for $\mathcal{A}_{j}^{P}$. Since
$\mathcal{A}_{j}^{P}\sqsubseteq\mathcal{A}_{\ell-1}^{P}\sqsubseteq\mathcal{B}^{\star}$,
we deduce that $x_{j}$ is removable from $X_{j}$ for $\mathcal{B}^{\star}$.

Let $j\in\\{i,\dots,t\\}$. The vertex $x_{j}$ is not minimal in at most one
block of $\mathcal{B}$ for $X_{j}$. We claim that $N(x_{j})$ is minimal in
$B_{1}^{\mathsf{max}}$ for $X_{j}$. Since the partition $\mathcal{B}^{\star}$
is obtained from $\mathcal{B}$ by splitting the block $B_{1}$ into
$B_{1}^{\star}$ and $B_{1}^{\mathsf{max}}$, this implies that $x_{j}$ is
removable from $X_{j}$ for $\mathcal{B}^{\star}$. We prove that $N(x_{j})$ is
minimal in $B_{1}^{\mathsf{max}}$ for $X_{j}$ by showing that, for every
$x_{\ell}\in X_{i}$, we have $B_{1}^{\mathsf{max}}\subseteq N(x_{\ell})$.

Since $A_{1}\subseteq\mathsf{notmin}(w,X_{i},\mathcal{A}_{i-1}^{P})$, we have
$N(w)\cap A_{1}\neq\varnothing$ and thus $w\in
X\text{-}\mathsf{max}_{\cap}(A_{1})$. Let $A$ be a block of
$\mathcal{A}_{i-1}^{P}$ contained in $B_{1}^{\mathsf{max}}$. As
$A_{1}\leqslant_{X}A$, we deduce that $w\in X\text{-}\mathsf{min}_{\cap}(A)$,
that is $A\subseteq N(w)$. By definition, $A$ is not contained in
$\mathsf{notmin}(w,X_{i},\mathcal{A}_{i-1}^{P})$ and thus $N(w)$ is minimal in
$A$ for $X_{i}$. Consequently, for every $x_{\ell}\in X_{i}$, we have
$A\subseteq N(x_{\ell})$. As this holds for every $A\subseteq
B_{1}^{\mathsf{max}}$, we deduce that $B_{1}^{\mathsf{max}}\subseteq
N(x_{\ell})$ for every $x_{\ell}\in X_{i}$. This ends the proof of Claim 7.

From now, based on Claim 7, we assume that $B_{1}^{\mathsf{max}}=\varnothing$.
We construct $\mathcal{B}_{\mathsf{new}}$ as follows. Recall that
$A_{1}\subseteq B_{1}$. We create a new block $\widehat{B}_{1}=B_{1}\cup
A_{2}\cup\dots\cup A_{k}$, and for every block $B\in\mathcal{B}$ such that
$B\neq B_{1}$, we create a new block
$\widehat{B}=B\setminus(A_{2}\cup\dots\cup A_{k})$. We define
$\mathcal{B}_{\mathsf{new}}=\\{\widehat{B}_{1}\\}\cup\\{\widehat{B}\,:\,B\in\mathcal{B}\setminus\\{B_{1}\\}\text{
and }\widehat{B}\neq\varnothing\\}$. The construction of
$\mathcal{B}_{\mathsf{new}}$ is illustrated in Figure 7.

Figure 7: Construction of $\mathcal{B}_{\mathsf{new}}$ from $\mathcal{B}$ with
$k=5$. The blocks of $\mathcal{B}$ and $\mathcal{B}_{\mathsf{new}}$ are in
blue, the blocks $A_{1},\dots,A_{5}$ of $\mathcal{A}_{i-1}^{P}$ contained in
$\mathsf{notmin}(w,X_{i},\mathcal{A}_{i-1}^{P})$ are in red, the other blocks
of $\mathcal{A}_{i-1}^{P}$ are in purple. In each block of $\mathcal{B}$ or
$\mathcal{B}_{\mathsf{new}}$, the blocks of $\mathcal{A}_{i-1}^{P}$ are
ordered w.r.t. $\leqslant_{X}$ from left to right.

We claim that $(X,\mathcal{B}_{\mathsf{new}})$ is a good partition that admits
a good permutation starting with $(x_{1},\dots,x_{i-1},w)$. By construction,
$\mathcal{B}_{\mathsf{new}}$ is a partition of $V(G)\setminus X$ and
$\mathcal{A}_{i-1}^{P}\sqsubseteq\mathcal{B}_{\mathsf{new}}$. As
$\mathsf{CC}(G-X)\sqsubseteq\mathcal{A}_{i-1}^{P}$ by definition, we have
$\mathsf{CC}(G-X)\sqsubseteq\mathcal{B}_{\mathsf{new}}$. So
$(X,\mathcal{B}_{\mathsf{new}})$ satisfies Property 1 of Definition 4.10.

Observe that for every block $\widehat{B}$ of $\mathcal{B}_{\mathsf{new}}$
such that $\widehat{B}\neq\widehat{B}_{1}$, $\widehat{B}$ is a subset of the
block $B$ of $\mathcal{B}$. Since $(X,\mathcal{B})$ is a good partition,
$G[X\cup B]$ is an $X$-interval graph and hence $G[X\cup\widehat{B}]$ is also
an $X$-interval graph. To prove that Property 2 is satisfied, it remains to
show that $G[X\cup\widehat{B}_{1}]$ is an $X$-interval graph, for which we
will use Claim 6.

Since $G[X\cup B_{1}]$ is an $X$-interval graph we know by Claim 5 that the
blocks of $\mathcal{A}_{i-1}^{P}$ contained in $B_{1}$ are pairwise comparable
for $\leqslant_{X}$. Since $B_{1}^{\mathsf{max}}=\varnothing$, for every block
$A\in\mathcal{A}_{i-1}^{P}$ such that $A\subseteq B_{1}$ and $A$ is not
contained in $\mathsf{notmin}(w,X_{i},\mathcal{A}_{i-1}^{P})$, we have
$A\leqslant_{X}A_{1}$. Moreover, we have
$A_{1}\leqslant_{X}\dots\leqslant_{X}A_{k}$. We deduce that the blocks of
$\mathcal{A}_{i-1}^{P}$ contained in $\widehat{B}_{1}$ are pairwise comparable
for $\leqslant_{X}$ because $\leqslant_{X}$ is transitive. By Claim 6, this
implies that $G[X\cup\widehat{B}_{1}]$ is an $X$-interval graph. We conclude
that Property 2 is satisfied.

It remains to prove that $(X,\mathcal{B}_{\mathsf{new}})$ admits a good
permutation starting with $(x_{1},\dots,x_{i-1},w)$. We prove it with the
following four claims.

######  Claim 8.

For every $j\in[i-1]$, $x_{j}$ is removable from $X_{j}$ for
$\mathcal{B}_{\mathsf{new}}$ and $w$ is removable from $X_{i}$ for
$\mathcal{B}_{\mathsf{new}}$. Moreover, $N(w)$ is minimal for $X_{i}$ in every
block of $\mathcal{B}_{\mathsf{new}}$ different from $\widehat{B}_{1}$.

For every $j\in[i-1]$, we have
$\mathcal{A}_{j}^{P}\sqsubseteq\mathcal{A}_{i-1}^{P}$ and thus $x_{j}$ is
removable from $X_{j}$ for $\mathcal{A}_{i}^{P}$. By construction of
$\mathcal{B}_{\mathsf{new}}$, we have
$\mathcal{A}_{i-1}^{P}\sqsubseteq\mathcal{B}_{\mathsf{new}}$. We deduce that
$x_{j}$ is removable from $X_{j}$ for $\mathcal{B}_{\mathsf{new}}$ for every
$j\in[i-1]$. By construction of $\mathcal{B}_{\mathsf{new}}$, we have
$\mathsf{notmin}(w,X_{i},\mathcal{A}_{i-1}^{P})\subseteq\widehat{B}_{1}$.
Hence, $N(w)$ is minimal for $X_{i}$ in every block of
$\mathcal{B}_{\mathsf{new}}$ different from $\widehat{B}_{1}$. It follows that
$w$ is removable from $X_{i}$ for $\mathcal{B}_{\mathsf{new}}$.

Let $p\in\\{i,\dots,t\\}$ such that $x_{p}=w$.

######  Claim 9.

For every $j,\ell\in[t]$ such that $i\leqslant j<\ell$ and $p<\ell$, if
$N(x_{j})$ is minimal in $B_{1}$ for $X_{j}$, then
$N(x_{j})\cap\widehat{B}_{1}\subseteq N(x_{\ell})$.

Let $j,\ell\in[t]$ such that $i\leqslant j<\ell$ and $p<\ell$ and $N(x_{j})$
is minimal in $B_{1}$ for $X_{j}$. Assume towards a contradiction that
$N(x_{j})\cap\widehat{B}_{1}\not\subseteq N(x_{\ell})$. It follows that
$N(x_{\ell})\cap\widehat{B}_{1}\subset N(x_{j})$ because
$G[X\cup\widehat{B}_{1}]$ is an $X$-interval graph (these neighborhoods in
$\widehat{B}_{1}$ are comparable). As $N(x_{j})$ is minimal in $B_{1}$ for
$X_{j}$ and $\ell\in X_{i}$, we have111In fact, we have $N(x_{j})\cap
B_{1}=N(x_{\ell})\cap B_{1}$ since $B_{1}\subseteq\widehat{B}_{1}$ and
$N(x_{\ell})\cap\widehat{B}_{1}\subset N(x_{i})$. $N(x_{j})\cap B_{1}\subseteq
N(x_{\ell})$. So by construction of $\widehat{B}_{1}$, there exists a block
$A\in\mathcal{A}_{i-1}^{P}$ such that $A\subseteq\widehat{B}_{1}\setminus
B_{1}$ and $N(x_{\ell})\cap A\subset N(x_{j})\cap A$. This implies that
$x_{\ell}\notin X\text{-}\mathsf{min}_{\cap}(A)$. Since
$A\subseteq\widehat{B}_{1}\setminus
B_{1}\subseteq\mathsf{notmin}(w,X_{i},\mathcal{A}_{i-1}^{P})$ and
$A\not\subseteq B_{1}$, we have $A_{1}\leqslant_{X}A$ and thus
$X\text{-}\mathsf{max}_{\cap}(A_{1})\subseteq
X\text{-}\mathsf{min}_{\cap}(A)$. We deduce that $x_{\ell}\notin
X\text{-}\mathsf{max}_{\cap}(A_{1})$.

By definition $A_{1}\subseteq\mathsf{notmin}(w,X_{i},\mathcal{A}_{i-1}^{P})$
and thus $w\in X\text{-}\mathsf{max}_{\cap}(A_{1})\subseteq
X\text{-}\mathsf{min}_{\cap}(A)$. Hence, we have $N(x_{\ell})\cap A\subset
N(w)\cap A$ and $N(x_{\ell})\cap A_{1}\subset N(w)\cap A_{1}$. Since $p<\ell$
and $w=x_{p}$, we have $x_{\ell}\in X_{p}$. Consequently, $N(w)$ is not
minimal in $A$ and $A_{1}$ for $X_{p}$. Let $B_{A}$ be the block of
$\mathcal{B}$ containing $A$. Since $A_{1}\subseteq B_{1}$ and $A\subseteq
B_{A}$, $N(w)$ is not minimal in $B_{1}$ and $B_{A}$ for $X_{p}$. But $B_{1}$
and $B_{A}$ are two distinct blocks of $\mathcal{B}$ because $A\not\subseteq
B_{1}$, this is a contradiction with $w$ being removable from $X_{p}$ for
$\mathcal{B}$.

######  Claim 10.

For every $j\in\\{p+1,\dots,t\\}$, the vertex $x_{j}$ is removable from
$X_{j}$ for $\mathcal{B}_{\mathsf{new}}$.

Let $j\in\\{p+1,\dots,t\\}$. The vertex $x_{j}$ is removable from $X_{j}$ from
$\mathcal{B}$. So there exists a block $B_{x_{j}}\in\mathcal{B}$ such that
$N(x_{j})$ is minimal for $X_{j}$ in every block of $\mathcal{B}$ different
from $B_{x_{j}}$. By construction, every block $\widehat{B}$ of
$\mathcal{B}_{\mathsf{new}}$ is associated with a block $B$ of $\mathcal{B}$
and if $B\neq B_{1}$, we have $B\subseteq\widehat{B}$. Thus, for every block
$\widehat{B}\in\mathcal{B}_{\mathsf{new}}$ different from $B_{1}$ and
$B_{x_{j}}$, $N(x_{j})$ is minimal in $\widehat{B}$ for $X_{j}$ because
$\widehat{B}\subseteq B$ and $N(x_{j})$ is minimal in $B$ for $X_{j}$. If
$B_{x_{j}}=B_{1}$, then $x_{j}$ is removable from $X_{j}$ for
$\mathcal{B}_{\mathsf{new}}$.

Now suppose that $B_{x_{j}}\neq B_{1}$. It follows that $N(x_{j})$ is minimal
for $X_{j}$ in $B_{1}$. As $p<j$, by Claim 9, for every $\ell>j$,
$N(x_{j})\cap\widehat{B}_{1}\subseteq N(x_{\ell})$. Thus, $N(x_{j})$ is
minimal in $\widehat{B}_{1}$ for $X_{j}$. Consequently, $N(x_{j})$ is minimal
in every block of $\mathcal{B}_{\mathsf{new}}$ different from
$\widehat{B}_{x_{j}}$. In both cases, $x_{j}$ is removable from $X_{j}$ for
$\mathcal{B}_{\mathsf{new}}$.

It remains to deal with the vertices of $(x_{1},\dots,x_{t})$ between $x_{i}$
and $x_{p-1}$.

######  Claim 11.

There exists a permutation $(x^{\star}_{i+1},\dots,x^{\star}_{p})$ of
$\\{x_{i},\dots,x_{p-1}\\}$ such that, for every $j\in\\{i+1,\dots,p\\}$,
$x^{\star}_{j}$ is removable from $\\{x^{\star}_{j},\dots,x^{\star}_{p}\\}\cup
X_{p+1}$ for $\mathcal{B}_{\mathsf{new}}$.

Since $(x_{1},\dots,x_{t})$ is a good permutation of $(X,\mathcal{B})$, for
every $j\in\\{i,\dots,p-1\\}$, there exists a block $B_{x_{j}}$ of
$\mathcal{B}$ such that $N(x_{j})$ is minimal for $X_{j}$ in every block of
$\mathcal{B}$ different from $B_{x_{j}}$. Let $j\in\\{i,\dots,p-1\\}$. We
start by proving that ($\spadesuit$) $N(x_{j})$ is minimal for $X_{i}$ in
every block of $\mathcal{B}_{\mathsf{new}}$ different from
$\widehat{B}_{x_{j}}$ and $\widehat{B}_{1}$. Take
$\widehat{B}\in\mathcal{B}_{\mathsf{new}}$ different from
$\widehat{B}_{x_{j}}$ and $\widehat{B}_{1}$. By construction, $\widehat{B}$ is
associated with a block $B$ of $\mathcal{B}$. Since
$\widehat{B}\neq\widehat{B}_{x_{j}}$, $N(x_{j})$ is minimal in $B$ for
$X_{j}$. As $j<p$ and $w=x_{p}$, we have $w\in X_{j}$ and thus $N(x_{j})\cap
B\subseteq N(w)$. By Claim 8, $N(w)$ is minimal for $X_{i}$ in every block of
$\mathcal{B}_{\mathsf{new}}$ different from $\widehat{B}_{1}$. In particular,
$N(w)$ is minimal in $\widehat{B}$ for $X_{i}$. As $N(x_{j})\cap B\subseteq
N(w)$ and $\widehat{B}\subseteq B$, we deduce that $N(x_{j})$ is also minimal
in $\widehat{B}$ for $X_{i}$. This proves ($\spadesuit$).

Since $G[X\cup\widehat{B}_{1}]$ is an $X$-interval graph, the neighborhoods of
$X$ in $\widehat{B}_{1}$ are pairwise comparable for the inclusion. Thus,
there exists a permutation $(x_{i+1}^{\star},\dots,x_{p}^{\star})$ of
$\\{x_{i},\dots,x_{p-1}\\}$ such that
$N(x_{i+1}^{\star})\cap\widehat{B}_{1}\subseteq
N(x_{i+2}^{\star})\cap\widehat{B}_{1}\subseteq\dots\subseteq
N(x_{p}^{\star})\cap\widehat{B}_{1}$.

Let $j\in\\{i+1,\dots,p\\}$ and
$X_{j}^{\star}=\\{x^{\star}_{j},\dots,x^{\star}_{p}\\}\cup X_{p+1}$. We need
to show that $x^{\star}_{j}$ is removable from $X_{j}^{\star}$ for
$\mathcal{B}_{\mathsf{new}}$. As $X_{j}^{\star}$ is a subset of $X_{i}$, from
($\spadesuit$), we know that $N(x_{j}^{\star})$ is minimal for $X_{j}^{\star}$
in every block of $\mathcal{B}_{\mathsf{new}}$ different from
$\widehat{B}_{1}$ and $\widehat{B}_{x_{j}^{\star}}$. Thus, if
$\widehat{B}_{1}=\widehat{B}_{x_{j}^{\star}}$, then $x_{j}^{\star}$ is
removable from $X_{j}^{\star}$ for $\mathcal{B}_{\mathsf{new}}$.

Suppose that $\widehat{B}_{1}\neq\widehat{B}_{x_{j}^{\star}}$. Then
$N(x_{j}^{\star})$ is minimal in $\widehat{B}_{1}$ for $X_{q}$ with $q\in[t]$
such that $x_{j}^{\star}=x_{q}$. By Claim 9, for every $x_{\ell}\in X_{p+1}$,
we have $N(x_{j}^{\star})\cap\widehat{B}_{1}\subseteq N(x_{\ell})$. Since
$N(x_{j}^{\star})\cap\widehat{B}_{1}\subseteq
N(x_{j+1}^{\star})\cap\widehat{B}_{1}\subseteq\dots\subseteq
N(x_{p}^{\star})\cap\widehat{B}_{1}$ and
$X_{j}^{\star}=\\{x^{\star}_{j},\dots,x^{\star}_{p}\\}\cup X_{p+1}$,
$N(x_{j})$ is minimal for $X_{j}^{\star}$ in $\widehat{B}_{1}$. We deduce that
$N(x_{j}^{\star})$ is minimal for $X_{j}^{\star}$ in every block of
$\mathcal{B}_{\mathsf{new}}$ different from $\widehat{B}_{x_{j}^{\star}}$.
Thus, $x_{j}^{\star}$ is removable from $X_{j}^{\star}$ for
$\mathcal{B}_{\mathsf{new}}$.

Let $(x^{\star}_{i+1},\dots,x^{\star}_{p})$ be the permutation of
$\\{x_{i},\dots,x_{p-1}\\}$ satisfying the condition of Claim 11. Take
$P_{\mathsf{new}}=(x_{1},\dots,x_{i-1},w,x^{\star}_{i+1},\dots,x^{\star}_{p},x_{p+1},\dots,x_{t})$,
from Claims 8, 10 and 11, we deduce that $P_{\mathsf{new}}$ is a good
permutation of $(X,\mathcal{B}_{\mathsf{new}})$. Hence,
$(X,\mathcal{B}_{\mathsf{new}})$ satisfies Property 3 of Definition 4.10 and
$(X,\mathcal{B}_{\mathsf{new}})$ is a good partition of $G$. As
$P_{\mathsf{new}}$ starts with $(x_{1},\dots,x_{i-1},w)$, this concludes the
proof of Lemma 4.18.

######  Lemma 4.21.

If $G$ has a good partition then Algorithm 1 returns one.

######  Proof 4.22.

Suppose $G$ admits a good partition with central clique $X$. We prove the
following invariant holds at the end of the $i$-th iteration of the while loop
for $X$.

Invariant. $G$ admits a good permutation starting with $w_{1},...,w_{i}$.

By assumption, $X$ admits a good permutation and thus the invariant holds
before the algorithm starts the first iteration of the while loop. By
induction, assume the invariant holds when Algorithm 1 starts the $i$-th
iteration of the while loop. Let $L=(w_{1},\dots,w_{i-1})$ be the consecutive
vertices chosen at Line 1 before the start of iteration $i$ (observe that $L$
is empty when $i=1$). The invariant implies that there exists a good
permutation $P=(w_{1},\dots,w_{i-1},x_{i},x_{i+1},...,x_{t})$ of $G$ starting
with $L$. By Lemma 4.16, the graph
$G[X\cup\mathsf{notmin}(x_{i},\\{x_{i},\dots,x_{t}\\},\mathcal{A}_{i-1}^{P})]$
is an $X$-interval graph. Observe that $\mathcal{A}^{P}_{i-1}$ and
$\\{x_{i},\dots,x_{t}\\}$ are the values of the variables $\mathcal{A}$ and
$W$ when Algorithm 1 starts the $i$-th iteration. Thus, at the start of the
$i$-th iteration, there exists a vertex $w_{i}$ such that
$G[X\cup\mathsf{notmin}(w_{i},W,\mathcal{A})]$ is an $X$-interval graph.
Consequently, the algorithm does not return no at the $i$-th iteration and
chooses a vertex $w_{i}\in\\{x_{i},\dots,x_{t}\\}$ such that the graph
$G[X\cup\mathsf{notmin}(w_{i},\\{x_{i},\dots,x_{t}\\},\mathcal{A}^{P}_{i})]$
is an $X$-interval graph. By Lemma 4.18, $G$ admits a good permutation
starting with $(w_{1},\dots,w_{i-1},w_{i})$. Thus, the invariant holds at the
end of the $i$-th iteration. If at the end of the $i$-th iteration $W$ is
empty, then the while loop stops and the algorithm returns a pair
$(X,\mathcal{A})$. Otherwise, the algorithm starts an $i+1$-st iteration and
the invariant holds at the start of this new iteration. By induction, the
invariant holds at every step and Algorithm 1 returns a pair $(X,\mathcal{A})$
which is a good partition by Lemma 4.14.

######  Theorem 4.23.

Algo. 1 decides in polynomial time if $G$ admits a star NeS model.

######  Proof 4.24.

By Theorem 4.11 $G$ admits a star NeS model iff $G$ admits a good partition,
and by Lemmata 4.14 and 4.21 Algorithm 1 finds a good partition iff the input
graph has a good partition. Let us argue for the runtime. Checking that $G$ is
chordal and finding the $O(n)$ maximal cliques can be done in polynomial time
[16, 24]. Given $X,Y\subseteq V(G)$ we check whether $G[X\cup Y]$ is an
$X$-interval graph, as follows. Take $G^{\prime}$ the graph obtained from
$G[X\cup Y]$ by adding $u$ and $v$ such that $N(u)=\\{v\\}$ and
$N(v)=\\{u\\}\cup X$. It is easy to see that $G[X\cup Y]$ is an $X$-interval
graph iff $G^{\prime}$ is an interval graph, which can be checked in
polynomial time.

##  5 Conclusion

The question if leaf powers can be recognized in polynomial time was raised
over 20 years ago [23], and this problem related to phylogenetic trees still
remains wide open. We have shown that polynomial-time recognition can be
achieved if the weighted leaf root is required to be a caterpillar (using the
connection to blue-red interval graphs and co-TT graphs) or if the NeS model
has a single large-degree branching.

We strongly believe our results could be combined to recognize in polynomial
time the graphs with a leaf root whose internal vertices induce a subdivided
star, that is a subdivided star with some leaves added to it (this generalizes
linear leaf powers as the internal vertices of a caterpillar induce a path).
Let us instead sketch how the techniques in this paper could be generalized to
handle the general case of leaf powers. Given a NeS model
$\mathcal{N}=(\mathcal{T},(T_{v})_{v\in V(G)})$ of a graph $G$ with
$\mathcal{T}$ the embedding of a tree $T$, we define the _topology_ of
$\mathcal{N}$ as the pair $(T^{\prime},(X_{u})_{u\in V(T^{\prime})})$ where
$T^{\prime}$ is the subtree induced by the internal nodes of $T$ and for each
node $u$ of $T^{\prime}$, we define $X_{u}=\\{v\in V(G):u\in T_{v}\\}$, which
will be a clique of $G$. For a star NeS model, $T^{\prime}$ is a single node
and we proved that (1) if a graph admits a star NeS model, then it admits one
where the only clique in the topology is maximal and (2) given a topology with
$T^{\prime}$ a single node, we can decide in polynomial time whether the graph
admits a star NeS model with this topology. For the general case it would
suffice to solve the following problems:

  * •

Problem 1: given a graph $G$ compute in polynomial time a polynomial-sized
family $\mathcal{F}$ of topologies such that $G$ is a leaf power if and only
if $G$ admits a NeS model with topology in $\mathcal{F}$. A first step towards
solving this problem would be to generalize Claim 3 to show that we can always
modify a NeS model so that all the cliques of its topology become maximal
cliques (or minimal separators, as these are also manageable in chordal
graphs). A second step is to study the structural properties of strongly
chordal graphs with the aim of showing a connection between these properties
and a family $\mathcal{F}$ of topologies of NeS models. One candidate among
these structural properties is the notion of _clique arrangements_ introduced
by Nevries and Rosenke [21, 22], which describes the intersections between the
maximal cliques of a chordal graph $G$ more precisely than the clique trees.

  * •

Problem 2: given a graph and a topology, construct a NeS model with this
topology or confirm that no such NeS model exists, in polynomial time. For
star NeS models, this is handled inside the for loop of Algorithm 1 and relies
on Definition 4.10. A step towards solving this problem would be to generalize
the combinatorial definition of a good partition to handle any topology.

We suggest to first employ this two-problems approach to graphs admitting NeS
models with a very simple topology. Natural first cases are topologies
$(T,(X_{u})_{u\in V(T)})$ where either $T$ is an edge or where $\bigcup_{u\in
V(T)}X_{u}$ is a clique. Both these restrictions generalize the topologies of
star NeS models and positive results should produce tools useful to attack the
general case.

Let us end with a subproblem whose solution would simplify this approach
towards settling the general case. Inspired by blue-red interval graphs, we
can define blue-red NeS models where the red vertices induce an independent
set and for every red vertex $v$ its neighbors are the blue vertices $u$ such
that $T_{v}\subseteq T_{u}$. We can adapt the proof of Theorem 3.2 to show
that $G$ admits a NeS model iff $G$ has a blue-red NeS model where the blue
vertices are simplicial vertices without true twins, so these have the same
modeling power. However, for blue-red NeS models the necessary topologies can
be significantly simpler. For example, NeS models of linear leaf powers are
caterpillars, whose topologies are paths, while its blue-red NeS models can be
restricted to an edge, whose topology is empty. Can we generalize the concept
of blue-red NeS models so that we can recursively color more vertices blue (by
allowing some of them to be adjacent under some conditions) and thereby
simplify the topologies we need to consider to solve Problems 1 and 2?

## References

  * [1] Eric Bibelnieks and Perino M. Dearing.  Neighborhood subtree tolerance graphs.  Discret. Appl. Math., 43(1):13–26, 1993.  doi:10.1016/0166-218X(93)90165-K.
  * [2] Andreas Brandstädt and Christian Hundt.  Ptolemaic graphs and interval graphs are leaf powers.  In LATIN 2008: Theoretical Informatics, 8th Latin American Symposium, Búzios, Brazil, April 7-11, 2008, Proceedings, volume 4957 of Lecture Notes in Computer Science, pages 479–491. Springer, 2008.  doi:10.1007/978-3-540-78773-0\\_42.
  * [3] Andreas Brandstädt, Christian Hundt, Federico Mancini, and Peter Wagner.  Rooted directed path graphs are leaf powers.  Discret. Math., 310(4):897–910, 2010.  doi:10.1016/j.disc.2009.10.006.
  * [4] Andreas Brandstädt and Van Bang Le.  Structure and linear time recognition of 3-leaf powers.  Inf. Process. Lett., 98(4):133–138, 2006.  doi:10.1016/j.ipl.2006.01.004.
  * [5] Andreas Brandstädt, Van Bang Le, and R. Sritharan.  Structure and linear-time recognition of 4-leaf powers.  ACM Trans. Algorithms, 5(1):11:1–11:22, 2008.  doi:10.1145/1435375.1435386.
  * [6] Tiziana Calamoneri, Antonio Frangioni, and Blerina Sinaimeri.  Pairwise compatibility graphs of caterpillars.  Comput. J., 57(11):1616–1623, 2014.  doi:10.1093/comjnl/bxt068.
  * [7] Tiziana Calamoneri and Blerina Sinaimeri.  Pairwise compatibility graphs: A survey.  SIAM Rev., 58(3):445–460, 2016.  doi:10.1137/140978053.
  * [8] Maw-Shang Chang and Ming-Tat Ko.  The 3-steiner root problem.  In Andreas Brandstädt, Dieter Kratsch, and Haiko Müller, editors, Graph-Theoretic Concepts in Computer Science, 33rd International Workshop, WG 2007, Dornburg, Germany, June 21-23, 2007. Revised Papers, volume 4769 of Lecture Notes in Computer Science, pages 109–120. Springer, 2007.  doi:10.1007/978-3-540-74839-7\\_11.
  * [9] Alexander Davis, Ruli Gao, and Nicholas Navin.  Tumor evolution: Linear, branching, neutral or punctuated?  Biochimica et Biophysica Acta (BBA) - Reviews on Cancer, 1867(2):151–161, 2017.  Evolutionary principles - heterogeneity in cancer?  doi:https://doi.org/10.1016/j.bbcan.2017.01.003.
  * [10] Reinhard Diestel.  Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics.  Springer, 2012.
  * [11] Michael Dom, Jiong Guo, Falk Hüffner, and Rolf Niedermeier.  Extending the tractability border for closest leaf powers.  In Dieter Kratsch, editor, Graph-Theoretic Concepts in Computer Science, 31st International Workshop, WG 2005, Metz, France, June 23-25, 2005, Revised Selected Papers, volume 3787 of Lecture Notes in Computer Science, pages 397–408. Springer, 2005.  doi:10.1007/11604686\\_35.
  * [12] Guillaume Ducoffe.  The 4-steiner root problem.  In Ignasi Sau and Dimitrios M. Thilikos, editors, Graph-Theoretic Concepts in Computer Science - 45th International Workshop, WG 2019, Vall de Núria, Spain, June 19-21, 2019, Revised Papers, volume 11789 of Lecture Notes in Computer Science, pages 14–26. Springer, 2019.  doi:10.1007/978-3-030-30786-8\\_2.
  * [13] David Eppstein and Elham Havvaei.  Parameterized leaf power recognition via embedding into graph products.  Algorithmica, 82(8):2337–2359, 2020.  doi:10.1007/s00453-020-00720-8.
  * [14] Petr A. Golovach, Pinar Heggernes, Nathan Lindzey, Ross M. McConnell, Vinícius Fernandes dos Santos, Jeremy P. Spinrad, and Jayme Luiz Szwarcfiter.  On recognition of threshold tolerance graphs and their complements.  Discret. Appl. Math., 216:171–180, 2017.  doi:10.1016/j.dam.2015.01.034.
  * [15] Martin Charles Golumbic, Nirit Lefel Weingarten, and Vincent Limouzy.  Co-tt graphs and a characterization of split co-tt graphs.  Discret. Appl. Math., 165:168–174, 2014.  doi:10.1016/j.dam.2012.11.014.
  * [16] Michel Habib, Ross M. McConnell, Christophe Paul, and Laurent Viennot.  Lex-bfs and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing.  Theor. Comput. Sci., 234(1-2):59–84, 2000.  doi:10.1016/S0304-3975(97)00241-7.
  * [17] Lars Jaffke, O-joung Kwon, Torstein J. F. Strømme, and Jan Arne Telle.  Mim-width III. graph powers and generalized distance domination problems.  Theor. Comput. Sci., 796:216–236, 2019.  doi:10.1016/j.tcs.2019.09.012.
  * [18] Manuel Lafond.  On strongly chordal graphs that are not leaf powers.  In Graph-Theoretic Concepts in Computer Science - 43rd International Workshop, WG 2017, Eindhoven, The Netherlands, June 21-23, 2017, Revised Selected Papers, pages 386–398, 2017.  doi:10.1007/978-3-319-68705-6\\_29.
  * [19] Manuel Lafond.  Recognizing k-leaf powers in polynomial time, for constant k.  In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1384–1410. SIAM, 2022.  URL: https://epubs.siam.org/doi/abs/10.1137/1.9781611977073.58, arXiv:https://epubs.siam.org/doi/pdf/10.1137/1.9781611977073.58, doi:10.1137/1.9781611977073.58.
  * [20] Clyde L. Monma, Bruce A. Reed, and William T. Trotter.  Threshold tolerance graphs.  J. Graph Theory, 12(3):343–362, 1988.  doi:10.1002/jgt.3190120307.
  * [21] Ragnar Nevries and Christian Rosenke.  Characterizing and computing the structure of clique intersections in strongly chordal graphs.  Discrete Applied Mathematics, 181:221–234, 2015.  URL: https://www.sciencedirect.com/science/article/pii/S0166218X14003941, doi:https://doi.org/10.1016/j.dam.2014.09.003.
  * [22] Ragnar Nevries and Christian Rosenke.  Towards a characterization of leaf powers by clique arrangements.  Graphs Comb., 32(5):2053–2077, 2016.  doi:10.1007/s00373-016-1707-x.
  * [23] Naomi Nishimura, Prabhakar Ragde, and Dimitrios M. Thilikos.  On graph powers for leaf-labeled trees.  J. Algorithms, 42(1):69–108, 2002.  doi:10.1006/jagm.2001.1195.
  * [24] Donald J. Rose, Robert Endre Tarjan, and George S. Lueker.  Algorithmic aspects of vertex elimination on graphs.  SIAM J. Comput., 5(2):266–283, 1976.  doi:10.1137/0205021.
  * [25] Erfan Sadeqi Azer, Mohammad Haghir Ebrahimabadi, Salem Malikić, Roni Khardon, and S. Cenk Sahinalp.  Tumor phylogeny topology inference via deep learning.  iScience, 23(11):101655, 2020.  doi:https://doi.org/10.1016/j.isci.2020.101655.
  * [26] A. Tamir.  A class of balanced matrices arising from location problems.  Siam Journal on Algebraic and Discrete Methods, 4:363–370, 1983\.