11institutetext: Dept. of Computer Science and Engineering, University of
Ioannina, Greece 22institutetext<EMAIL_ADDRESS>33institutetext:
0000-0001-6684-8459<EMAIL_ADDRESS>44institutetext: 0000-0001-8630-3835;
<EMAIL_ADDRESS>
# Adding a Tail in Classes of Perfect Graphs††thanks:  Research at the
University of Ioannina supported by the Hellenic Foundation for Research and
Innovation (H.F.R.I.) under the “First Call for H.F.R.I. Research Projects to
support Faculty members and Researchers and the procurement of high-cost
research equipment grant”, Project FANTA (eFficient Algorithms for NeTwork
Analysis), number HFRI-FM17-431.

Anna Mpanti 1122 Stavros D. Nikolopoulos 1133 Leonidas Palios 1144

###### Abstract

Consider a graph $G$ which belongs to a graph class ${\cal C}$. We are
interested in connecting a node $w\not\in V(G)$ to $G$ by a single edge $uw$
where $u\in V(G)$; we call such an edge a _tail_. As the graph resulting from
$G$ after the addition of the tail, denoted $G+uw$, need not belong to the
class ${\cal C}$, we want to compute a minimum ${\cal C}$-completion of $G+w$,
i.e., the minimum number of non-edges (excluding the tail $uw$) to be added to
$G+uw$ so that the resulting graph belongs to ${\cal C}$.

In this paper, we study this problem for the classes of split, quasi-
threshold, threshold, and $P_{4}$-sparse graphs and we present linear-time
algorithms by exploiting the structure of split graphs and the tree
representation of quasi-threshold, threshold, and $P_{4}$-sparse graphs.

###### Keywords:

edge addition completion split graph quasi-threshold graph threshold graph
$P_{4}$-sparse graph

##  1 Introduction

Given a graph $G$, an edge connecting a vertex $w\not\in V(G)$ to a vertex $u$
of $G$ is a _tail_ added to $G$; let us denote the resulting graph as $G+uw$.
If $G$ belongs to a class ${\cal C}$ of graphs, this may not hold for the
graph $G+uw$. Hence, we are interested in computing a minimum ${\cal
C}$-completion of $G+uw$, i.e., the minimum number of non-edges (excluding the
tail $uw$) to be added to $G+uw$ so that the resulting graph belongs to ${\cal
C}$; such non-edges are called _fill edges_. The above problem is an instance
of the more general (${\cal C},+k$)-MinEdgeAddition problem [22] in which we
add $k$ given non-edges in a graph belonging to a class ${\cal C}$ and we want
to compute a minimum ${\cal C}$-completion of the resulting graph.

Computing a minimum completion of an arbitrary graph into a specific graph
class is an important and well studied problem with applications in areas
involving graph modeling with missing edges due to lacking data, e.g.,
molecular biology and numerical algebra [9, 19, 25]. Unfortunately, minimum
completions into many interesting graph classes, such as split graphs, chordal
graphs and cographs, are NP-hard to compute [2, 8, 16, 30]. This led the
researchers towards the computation of minimal completions, the solution of
problems with restricted input, and approximation or parameterized algorithms.

A related field is that of the dynamic recognition (or on-line maintenance)
problem on graphs: a series of requests for the addition or the deletion of an
edge or a vertex (potentially incident on a number of edges) are submitted and
each is executed only if the resulting graph remains in the same class of
graphs. Several authors have studied this problem for different classes of
graphs and have given algorithms supporting some or all the above operations;
we mention the edges-only fully dynamic algorithm of Ibarra [13] for chordal
and split graphs, and the fully dynamic algorithms of Hell et al. [11] for
proper interval graphs, of Shamir and Sharan [26] for cographs, of Heggernes
and Mancini for split graphs [10], and of Nikolopoulos et al. for
$P_{4}$-sparse graphs [23].

In this paper, we exploit the structure of split graphs and the tree
representation of quasi-threshold, threshold, and $P_{4}$-sparse graphs in
order to present algorithms for computing a minimum completion of a given
graph $G$ in each of these classes to which we have added a tail. Given the
($K,S$)-partition of a given split graph or the tree representation of a given
quasi-threshold, threshold, or $P_{4}$-sparse graph, our algorithms run in
optimal $O(n)$ time where $n$ is the number of vertices of $G$. These
algorithms are a first step towards the solution of the (${\cal
C},+1$)-MinEdgeAddition problem [22] for each of these four classes ${\cal C}$
of graphs.

##  2 Theoretical Framework

We consider finite undirected graphs with no loops or multiple edges. For a
graph $G$, we denote by $V(G)$ and $E(G)$ the vertex set and edge set of $G$,
respectively. Let $S$ be a subset of the vertex set $V(G)$ of a graph $G$.
Then, the subgraph of $G$ induced by $S$ is denoted by $G[S]$. The
neighborhood $N_{G}(x)$ of a vertex $x$ of the graph $G$ is the set of all the
vertices of $G$ which are adjacent to $x$. The closed neighborhood of $x$ is
defined as $N_{G}[x]:=N_{G}(x)\cup\\{x\\}$. The degree of a vertex $x$ in $G$,
denoted $deg(x)$, is the number of vertices adjacent to $x$ in $G$; thus,
$deg(x)=|N_{G}(x)|$. A vertex of a graph is _universal_ if it is adjacent to
all other vertices of the graph. We extend this notion to a subset of the
vertices of a graph $G$ and we say that a vertex is _universal in a set_
$S\subseteq V(G)$, if it is universal in the induced subgraph $G[S]$. Finally,
$C_{k}$ ($P_{k}$ resp.) denotes the chordless cycle (chordless path resp.) on
$k$ vertices; in each $P_{4}$, the unique edge incident on its first or last
vertex is called a _wing_.

##  3 Split Graphs

The split graphs are of wide theoretical interest and have been the focus of
many research papers. An undirected graph $G$ is _split_ if its vertex set
$V(G)$ admits a partition into a clique $K$ and an independent set $S$ [7];
the partition into $K,S$ can be computed in time proportional to the size of
the graph. It also holds that a graph is split if and only if it contains no
induced $C_{4}$, $C_{5}$, or $2K_{2}$.

######  Lemma 1.

Let $G$ be a split graph with vertex partition into a clique $K$ and an
independent set $S$, $u$ a vertex of $G$, $uw$ a tail, and $K_{s}=\\{x\in
K\,|\,N_{G}(x)\cap S\neq\emptyset\\}$. Then, there exists a split-completion
for the graph $G+uw$ in which the number of fill edges needed is $0$ if $u\in
K$ and $|K_{s}|-deg_{G}(u)$ if $u\in S$.

###### Proof.

If $u\in K$, no fill edge (in addition to $uw$) is needed, which is optimal,
since $G+uw$ is a split graph with clique $K$ and independent set
$S\cup\\{w\\}$.

Now consider that $u\in S$. A split completion of $G+uw$ can be obtained by
connecting $u$ to all its non-neighbors in $K_{s}$; the resulting graph is
split with clique $K_{s}\cup\\{u\\}$ and independent set
$S\cup(K-K_{s})\cup\\{w\\}$. To prove its optimality, suppose for
contradiction that there existed a split completion of $G+uw$ that uses fewer
than $|K_{s}|-deg_{G}(u)$ fill edges. Then, there would exist a vertex $a\in
K_{s}\setminus N_{G}(u)$ which is not incident on any fill edge. If there
existed one more vertex $b\in K_{s}\setminus(N_{G}(u)\cup\\{a\\})$ not
incident on any fill edge as well, then the edges $ab$ and $uw$ would form a
$2K_{2}$, a contradiction. Then, all the fill edges would be incident on the
vertices in $K_{s}\setminus(N_{G}(u)\cup\\{a\\})$. But then, if $z$ is a
neighbor of $a$ in $S$, the edges $az$ and $uw$ would form a $2K_{2}$, a
contradiction. ∎

Since the vertices in the clique $K$ are all pairwise adjacent, we note that
$|K\setminus K_{s}|\leq 1$. The lemma directly implies that given the set
$K_{s}$, the minimum number of fill edges can be computed in $O(|V(G)|)$ time
otherwise the time complexity is $O(|V(G)|+|E(G)|)$.

Figure 1: The structure of the tree representation of a threshold graph [20]

##  4 Threshold and Quasi-threshold Graphs

Threshold Graphs. A well-known subclass of perfect graphs called threshold
graphs are those whose independent vertex set subsets can be distinguished by
using a single linear inequality. A graph $G$ is _threshold_ if there exists a
threshold assignment $[\alpha,t]$ consisting of a labeling $\alpha$ of the
vertices by non-negative integers and an integer threshold $t$ such that: a
set $S\subseteq V(G)$ is independent if and only if
$\alpha(v_{1})+\alpha(v_{2})+\cdots+\alpha(v_{p})\leq t$ where $v_{i}\in
S,1\leq i\leq p$. Chvátal and Hammer [3] first proposed threshold graphs in
1973 and have proved that the threshold graphs are precisely the graphs that
contain no induced $C_{4}$, $P_{4}$, or $2K_{2}$.

Nikolopoulos [20] proved that every threshold graph admits a unique rooted
tree representation as shown in Figure 1: each tree node is associated with a
vertex set $V_{i,j}$ (these sets partition the vertex set of the graph) with
each $V_{i,1}$ inducing a clique and each of the remaining sets containing a
single vertex (note that the tree nodes associated with these singleton sets
have no descendants) and the vertices in the union of the sets associated with
the nodes on a path of tree edges from a tree node to any one of its
descendants induce a clique. Thus, the vertices in $V_{k,1}$ are adjacent to
all the vertices in $\bigcup_{i>k}V_{i,j}$, the vertices in
$\bigcup_{i}\bigcup_{j\geq 2}V_{i,j}$ form an independent set, and the
vertices in $\bigcup_{i}V_{i,1}$ induce a clique.

Let $G$ be a threshold graph and consider adding a tail $uw$ to $G$ where
$u\in V(G)$. Then we can show the following lemma.

Figure 2: The tree representation of a quasi-threshold graph.

######  Lemma 2.

Let $G$ be a threshold graph and let its tree representation $T_{G}$ consist
of nodes associated with sets $V_{i,j}$ where $0\leq i\leq h$ and $1\leq j\leq
k_{i}$ (Figure 1). Consider the addition of a tail $uw$ where $u\in V(G)$.
Then, there exists a minimum threshold completion of the graph $G+uw$ using
$f$ fill edges (excluding $uw$) where:

  1. (i)

If $u\in V_{i,1}$, then $f\ =\ \min_{0\leq\ell\leq
i}\left\\{\left(\sum_{s=\ell+1}^{i}\sum_{t=2}^{k_{s}}|V_{s,t}|\right)+\sum_{s=0}^{\ell}|V_{s,1}|\right\\}$;

  2. (ii)

If $u\in V_{i,j}$ where $2\leq j\leq k_{i}$, then $f=\min\\{f_{1},f_{2}\\}$
where
$f_{1}\ =\ \sum_{r=i}^{h}|V_{r,1}|+\min_{i\leq\ell\leq
h}\left\\{\left(\sum_{s=\ell+1}^{h}\sum_{t=2}^{k_{s}}|V_{s,t}|\right)+\sum_{s=0}^{\ell}|V_{s,1}|\right\\}$
and
$f_{2}\ =\ \sum_{r=i}^{h}|V_{r,1}|+\min_{0\leq\ell\leq
i-1}\left\\{\left(\sum_{s=\ell+1}^{h}\sum_{t=2}^{k_{s}}|V_{s,t}|\right)+\sum_{s=0}^{\ell}|V_{s,1}|\right\\}-1$.

Quasi-threshold Graphs. A graph $G$ is called _quasi-threshold_ , or QT-graph
for short, if $G$ contains no induced $C_{4}$ or $P_{4}$ [6, 18, 27, 28]. The
class of quasi-threshold-graphs is a subclass of the class of cographs and
properly contains the class of threshold graphs [4, 5, 7, 29]. Nikolopoulos
and Papadopoulos [24] have shown, among other properties, a unique rooted tree
representation of QT-graphs which is a generalization of the tree
representation of threshold graphs (Figure 2): the tree nodes are associated
with disjoint vertex subsets each inducing a clique and the vertex sets
associated with the tree nodes in a path from a tree node to any of its
descendants induce a clique. It has been proven that a graph is QT-graph if
and only if it admits such a tree representation [17, 21]. Then, by
generalizing the approach for threshold graphs, we can show the following
lemma.

######  Lemma 3.

Let $G=(V,E)$ be a QT-graph, and let $T_{G}$ be its tree representation.
Consider the addition of a tail $uw$ incident on a node $u$ of $G$ and suppose
without loss of generality that $u\in V_{i,1}$ and that the vertex sets
associated with the tree nodes on the path from the root of $T_{G}$ to the
node associated with $V_{i,1}$ are in order $V_{0,1},V_{1,1},\ldots,V_{i,1}$.
Then, there exists a minimum QT completion of the graph $G+uw$, and the
minimum number of fill edges needed (excluding the tail $uw$) is
$\min_{0\leq\ell\leq
i}\left\\{\left(\sum_{s=\ell+1}^{i}\sum_{t=2}^{k_{s}}|V_{s,t}|\right)+\sum_{s=0}^{\ell}|V_{s,1}|\right\\}$

##  5 $P_{4}$-sparse Graphs

The $P_{4}$-sparse graphs are defined as the graphs for which every set of $5$
vertices induces at most one $P_{4}$ [12] (Figure 3 depicts the $7$ forbidden
subgraphs for the class of $P_{4}$-sparse graphs). The $P_{4}$-sparse graphs
are perfect and also perfectly orderable [12], and properly contain many graph
classes, such as, the cographs, the $P_{4}$-reducible graphs, etc. (see [1,
14, 15]). They have received considerable attention in recent years and find
applications in applied mathematics and computer science (e.g.,
communications, transportation, clustering, scheduling, computational
semantics) in problems that deal with graphs featuring “local density”
properties.

Figure 3: The forbidden subgraphs of the class of $P_{4}$-sparse graphs [15].

For a $P_{4}$-sparse graph either the graph or its complement is disconnected
with the connected components inducing $P_{4}$-sparse graphs, or induces a
spider. A graph $H$ is called a _spider_ if its vertex set $V(H)$ admits a
partition into sets $S,K,R$ such that:

  * •

the set $S$ is an independent set, the set $K$ is a clique, and $|S|=|K|\geq
2$;

  * •

every vertex in $R$ is adjacent to every vertex in $K$ and to no vertex in
$S$;

  * •

there exists a bijection $f:S\to K$ such that for each vertex $s\in S$ either
$N_{G}(s)\cap K=\\{f(s)\\}$ or $N_{G}(s)\cap K=K-\\{f(s)\\}$; in the former
case, the spider is _thin_ , in the latter it is _thick_ (see Figure 4).

Note that for $|S|=|K|=2$, the spider is simultaneously thin and thick. To
avoid ambiguity, in the following, for thick spiders we assume that $|K|\geq
3$.

Figure 4: (left) A thin spider; (right) a thick spider.

Figure 5:

In [15], Jamison and Olariu showed that each $P_{4}$-sparse graph $G$ admits a
unique tree representation, up to isomorphism, called the _$P_{4}$ -sparse
tree_ $T(G)$ of $G$, which is a rooted tree such that:

  * (i)

each internal node of $T(G)$ has at least $2$ children provided that
$|V(G)|\geq 2$;

  * (ii)

the internal nodes are labelled by one of $0$, $1$, or $2$ (_$0$ -, $1$-,
$2$-nodes, resp._) and the parent-node of each $0$\- or $1$-node $t$ has a
different label than $t$;

  * (iii)

the leaves of the $P_{4}$-sparse tree are in a $1$-to-$1$ correspondence with
the vertices of $G$; if the least common ancestor of the leaves corresponding
to two vertices $v_{i},v_{j}$ of $G$ is a $0$-node ($1$-node, resp.) then the
vertices $v_{i},v_{j}$ are non-adjacent (adjacent, resp.) in $G$, whereas the
vertices corresponding to the leaves of a subtree rooted at a $2$-node induce
a spider.

The structure of the $P_{4}$-sparse tree implies the following lemma.

######  Lemma 4.

Let $G$ be a $P_{4}$-sparse graph and let $H=(S,K,R)$ be a _thin_ spider of
$G$. Moreover, let $s\in S$ and $k\in K$ be vertices that are adjacent in the
spider.

P1. Every vertex of the spider is adjacent to all vertices in
$N_{G}(s)\setminus\\{k\\}$.

P2. Every vertex $z\in K\setminus\\{k\\}$ is adjacent to all vertices in
$N_{G}(k)\setminus\\{s,z\\}$.

Let $G$ be a given graph to which we want to add the tail $uw$ with $u\in
V(G)$. Let $t_{0}t_{1}\cdots t_{h}u$ be the path from the root $t_{0}$ of the
$P_{4}$-sparse tree $T_{G}$ of $G$ to the leaf associated with $u$. Moreover,
let $V_{i}$ ($0\leq i<h$) be the set of vertices associated with the leaves of
the subtrees rooted at the children of $t_{i}$ except for $t_{i+1}$ and
$V_{h}$ be the set of vertices associated with the leaves of the subtrees
rooted at the children of $t_{h}$ except for the leaf associated with $u$ (see
Figure 5). The sets $V_{0},V_{1},\ldots,V_{h}$ form a partition of
$V(G)\setminus\\{u\\}$.

We show that there always exists a minimum $P_{4}$-sparse completion of the
graph $G+uw$ exhibiting one of a small number of different formations for
$u,w$.

######  Lemma 5.

Let $G$ be a $P_{4}$-sparse graph and $T_{G}$ be its $P_{4}$-sparse tree.
Consider the addition of a tail $uw$ incident on a node $u$ of $G$. Then,
there exists a minimum $P_{4}$-sparse completion $G^{\prime}$ of the graph
$G+uw$ such that for the $P_{4}$-sparse tree $T_{G^{\prime}}$ of $G^{\prime}$,
one of the following three cases holds:

  1. 1.

The nodes $u,w$ in $T_{G^{\prime}}$ have the same parent-node which is a
$2$-node corresponding to a thin spider $(S,K,R)$ with $u\in K$ and $w\in S$.

  2. 2.

The $P_{4}$-sparse tree $T_{G^{\prime}}$ results from $T_{G}$ by replacing the
leaf for $u$ by the $3$-treenode Formation $1$ shown in Figure 6(left).

  3. 3.

The $P_{4}$-sparse tree $T_{G^{\prime}}$ results from $T_{G}$ by removing the
leaf for $u$ and replacing an $1$\- or a $2$-node $t$ in the path from the
root of $T_{G}$ to the leaf for $u$ by the $5$-treenode Formation $2$ in
Figure 6(right).

Figure 6: (left) Formation $1$; (right) Formation $2$ where $t$ is a 1- or a
2-node. Formation $1$ is a special case of Formation $2$ when $Z=\emptyset$.

###### Proof.

Let $G_{OPT}$ be a minimum $P_{4}$-sparse completion of the graph $G+uw$ and
let $T_{OPT}$ be its $P_{4}$-sparse tree. We consider the following cases:

A. The leaves associated with $u,w$ in $T_{OPT}$ do not have the same parent-
node: Let $T_{R}$ be the $P_{4}$-sparse tree obtained from $T_{OPT}$ by using
Formation $2$ just above the least common ancestor $t$ of $w$ and $u$ in
$T_{OPT}$ (Figure 7); let $G_{R}$ be the $P_{4}$-sparse graph corresponding to
the tree $T_{R}$. Then, $G_{R}$ uses no more fill edges than $T_{OPT}$. To see
this, let $t^{\prime}$ be the child of $t$ that is an ancestor of the leaf for
$u$ (note that $t^{\prime}$ may coincide with the leaf for $u$). Since $u,w$
are adjacent in $G_{OPT}$, $t$ is a $1$\- or a $2$-node. In either case, $w$
is adjacent to all vertices corresponding to the leaves of the subtree of
$T_{OPT}$ rooted at $t^{\prime}$ and all these edges, except for the tail
$uw$, are fill edges. If $t$ is a $1$-node, then $u$ is adjacent to all
vertices in $X$ (Figure 7) and thus $G_{R}$ uses no more fill edges. If $t$ is
a $2$-node then $u$ is adjacent to all the vertices in the clique $K_{X}$ of
the corresponding spider (which includes $w$). Moreover, because $w\in K_{X}$,
$w$ is adjacent to all the vertices in $K_{X}\setminus\\{w\\}$ and to at least
$1$ vertex in the independent set for a total of $|K_{X}|$ fill edges; these
fill edges can be used to connect $u$ to the vertices in the independent set
of the spider and thus $G_{R}$ uses no more fill edges in this case too.

Now, in the $P_{4}$-sparse tree $T_{R}$ in Figure 7(right), let
$A=V(G)\setminus(Z\cup\\{u\\})$. Recall that in the $P_{4}$-sparse tree
$T_{G}$ of $G$, the path from the root $t_{0}$ to $u$ is $t_{0}t_{1}\cdots
t_{h}u$ and $V_{i}$ ($0\leq i\leq h$) is the set of vertices associated with
the leaves of the subtrees rooted at the children of $t_{i}$ except for
$t_{i+1}$ (where $t_{h+1}$ is the leaf associated with $u$); see Figure 5.

We first observe that the induced subgraph $G_{R}[Z]$ induced by the set of
vertices $Z$ corresponding to the leaves of the subtree of $T_{R}$ rooted at
node $t$ coincides with the induced subgraph $G[Z]$ (otherwise $G_{OPT}$ would
include fill edges that could be removed in contradiction to its optimality);
then, let $t=t_{k}$. It also holds that node $t$ in $T_{R}$ is a $1$\- or a
$2$-node, since node $t$ was a $1$\- or a $2$-node in $T_{OPT}$, as well. Let
$A=V(G)\setminus(Z\cup\\{u\\})$. Note that there is no set $V_{j}$ such that
$x,y\in V_{j}$, $x$ is a neighbor of $u$ in $G$, $x\in V_{j}\cap A$ and $y\in
V_{j}\cap Z$, otherwise we can move $x$ to $Z$ along with $y$; because $y$ is
in $Z$, all adjacencies from $y$ to all the vertices in
$V(G)\setminus(V_{j}\cup\\{u\\})$ in $G$ are maintained and this will also
hold for $x$, and the fill edge $xw$ will be removed, a contradiction.
Similarly, there is no set $V_{j}$ such that $x,y\in V_{j}$, $y$ is a non-
neighbor of $u$ in $G$ and $x\in V_{j}\cap A$ and $y\in V_{j}\cap Z$ otherwise
we can move $y$ to $A$ along with $x$. This implies that for each
$i=0,1,\ldots,h$, either $V_{i}\subseteq A$ or $V_{i}\subseteq Z$, and since
$t=t_{k}$, $V_{k}\subseteq Z$.

Finally, there exists no $j>k$ such that $V_{j}\subseteq A$. Suppose that
there existed such a $V_{j}$ and let $j$ be the largest such index. Then,
because $t=t_{k}$ is a $1$\- or a $2$-node and $k<j$, there would exist vertex
$z\in V_{k}$ which would be adjacent to all vertices in $V_{j}$. This implies
that in $T_{R}$, the least common ancestor of $z$ and the vertices in $V_{k}$
would be a $1$-node. But then, if we moved $V_{j}$ to $Z$ then we would have
fewer fill edges, a contradiction. Therefore, the tree $T_{R}$ is as described
in Case $3$ of the statement of the lemma.

Figure 7: (left) The $P_{4}$-sparse tree $T_{OPT}$ in which the leaves for
$u,w$ do not have the same parent-node and have node $t$ as their least common
ancestor; (right) The $P_{4}$-sparse tree $T_{R}$ obtained by using Formation
$2$ just above node $t$ which results in no more fill edges than those in
$G_{OPT}$.

B. The leaves associated with $u,w$ in $T_{OPT}$ have the same parent-node
$p$: Then, since $u,w$ are adjacent, the parent-node $p$ is either an $1$-node
or a $2$-node.

  * (i)

The parent-node $p$ of $u,w$ in $T_{OPT}$ is an $1$-node: Then, the leaves
associated with $u$ and $w$ are the only children of $p$ (Formation $1$),
otherwise we can use Formation $2$ as shown in Figure 8 which requires fewer
fill edges. Then, $w$ will be adjacent to all neighbors of $u$ in $T_{OPT}$;
this and the optimality of $G_{OPT}$ imply that $T_{OPT}$ results from $T_{G}$
by replacing the leaf for $u$ by Formation $1$.

  * (ii)

The parent-node $p$ of $u,w$ in $T_{OPT}$ is a $2$-node: Let $H=(S,K,R)$ be
the corresponding spider. If $H$ is thick (thus $|K|\geq 3$), then no matter
whether the tail $uw$ is an $S$-$K$, $K$-$K$, or $R$-$K$ edge, the sum of
degrees of $u,w$ in $H$ (excluding $uw$) is at least $|V(H)|-3+|K|-2$
(consider an $S$-$K$ edge). However, we would have added no more fill edges if
we have made $u$ universal in $G[V(H)\setminus\\{w\\}]$ and then applied
Formation $2$ at the parent of the leaf for $u$ (then
$Z=V(H)\setminus\\{u,w\\}$) using $V(H)-2\leq V(H)+|K|-5$ fill edges.

In the same way, we show that we would have added no more fill edges if $H$ is
a thin spider and the tail $uw$ is a $K$-$K$ or $K$-$R$ edge. If $uw$ is an
$S$-$K$ edge with $u\in S$ and $w\in K$, then we exchange $u$ and $w$ for the
same total number of fill edges and get a thin spider with $u\in K$ and $w\in
S$.

∎

Figure 8: A transformation that reduces the number of fill edges.

###  5.1 Adding a Tail to a Spider

In this section, we consider adding a tail $uw$ to a spider
$H=(S_{H},K_{H},R_{H})$ where $u\in V(H)$. In the following two lemmas, we
address the cases of a thin or a thick spider $H$ respectively.

######  Lemma 6.

Consider the addition of a tail $uw$ to a _thin_ spider $H=(S_{H},K_{H}$,
$R_{H})$ where $u$ is a vertex of $H$. Then, for the number $f$ of fill edges
(excluding the tail $uw$) in a minimum $P_{4}$-sparse completion of the graph
$H+uw$, it holds:

  1. 1.

if $u\in S_{H}$, $f=|K_{H}|-1$ if $R_{H}=\emptyset$ and $f=|K_{H}|$ otherwise;

  2. 2.

if $u\in K_{H}$, $f=|K_{H}|-1$;

  3. 3.

if $u\in R_{H}$, then $f=\min\\{\,|R_{H}\setminus N_{H}[u]|,\
|K_{H}|+f^{\prime}\,\\}$ where $f^{\prime}$ is the number of fill edges
(excluding $uw$) in a minimum $P_{4}$-sparse completion of the graph
$H[R_{H}]+uw$.

###### Proof.

1\. Let $v\in K_{H}$ be the neighbor of $u$ in $H$. Then, we can get a
$P_{4}$-sparse graph as follows: if $R_{H}=\emptyset$, we connect $u$ to all
vertices in $K_{H}\setminus\\{v\\}$ (we get a thin spider with
$S=(S_{H}\setminus\\{u\\})\cup\\{w\\}$,
$K=(K_{H}\setminus\\{v\\})\cup\\{u\\}$, and $R=\\{v\\}$, that is, the tail
$uw$ is a wing of a $P_{4}$ of a thin spider), otherwise we connect $v$ to all
vertices in $\\{w\\}\cup(S_{H}\setminus\\{u\\})$, which makes $v$ universal in
$V(H)\cup\\{w\\}$ and $u,w$ form a separate connected component in
$G[V(G)\setminus\\{v\\}]$; the total number of fill edges (excluding the tail
$uw$) is precisely $|K_{H}|-1$ if $R_{H}=\emptyset$ and $K_{H}$ otherwise.

Moreover, this is the minimum number of fill edges (excluding $uw$) needed.
First, we note that for each pair $k_{i},s_{i}$ where $k_{i}\in
K_{H}\setminus\\{v\\}$ and $s_{i}\in S_{H}\setminus\\{u\\}$, the vertices
$v,u,w,k_{i},s_{i}$ define an $F_{5}$ or an $F_{3}$ depending on whether the
vertices $v,w$ are adjacent or not, which implies that at least $|K_{H}|-1$
fill edges (excluding $uw$) are needed. Then, if there is a way of getting a
$P_{4}$-sparse graph by adding fewer than the number of fill edges mentioned
in Case $1$ of the statement of the lemma, it has to be the case that (i)
$R_{H}\neq\emptyset$, (ii) each pair $k_{i},s_{i}$ where $k_{i}\in
K_{H}\setminus\\{v\\}$ and $s_{i}\in S_{H}\setminus\\{u\\}$ is incident on
exactly $1$ fill edge, and (iii) no more fill edges exist. Let $r\in R_{H}$
and $k\in K_{H}\setminus\\{v\\}$. Then, the vertices $v,u,w,k,r$ induce a
forbidden subgraph (an $F_{5}$ if $k$ is non-adjacent to both $u,w$, or an
$F_{6}$ ($F_{1}$, resp.) if $k$ becomes adjacent to $u$ ($w$, resp.) by means
of a fill edge); thus, at least $K_{H}$ fill edges are needed in this case.

2\. Let $v\in S_{H}$ be the neighbor in $H$ of $u\in K_{H}$. Then, by
connecting $u$ to all vertices in $S_{H}\setminus\\{v\\}$ (which makes $u$
universal in $H$) or by connecting $w$ to all vertices in
$K_{H}\setminus\\{u\\}$ yields a $P_{4}$-sparse graph. Moreover, this is the
minimum number of fill edges (excluding the tail $uw$) that need to be added.
Suppose, for contradiction, that we get a $P_{4}$-sparse graph after having
added fewer than $|K_{H}|-1$ fill edges (excluding $uw$) to the thin spider
$H$. Then, there exists a pair of adjacent vertices $s,k$ with $s\in
S_{H}\setminus\\{v\\}$ and $k\in K_{H}\setminus\\{u\\}$ such that neither $s$
nor $k$ is incident on a fill edge. Then the vertices $u,v,w,s,k$ induce a
forbidden subgraph $F_{5}$ or $F_{3}$ if $w$ and $v$ are adjacent or not,
respectively, a contradiction.

3\. The term $R_{H}\setminus N_{H}[u]$ corresponds to making $u$ universal in
$H[R_{H}]$ in which case the resulting graph is $P_{4}$-sparse (it is a thin
spider with $S=S_{H}\cup\\{w\\}$, $K=K_{H}\cup\\{u\\}$, and
$R=R_{H}\setminus\\{u\\}$). The term $|K_{H}|+f^{\prime}$ corresponds to
adding $|K_{H}|$ fill edges connecting $w$ to the vertices in $K_{H}$ and then
computing a minimum $P_{4}$-sparse completion of the graph $H[R_{H}]+uw$. Note
that no minimum $P_{4}$-sparse completion of $H+uw$ exists with $u$ not being
universal in $R_{H}$ and with using fewer than $|K_{H}|$ fill edges incident
on the vertices in $S_{H}\cup K_{H}$: if there were such a minimum
$P_{4}$-sparse completion $H^{\prime}$ of $H+uw$, then in $H^{\prime}$, there
would exist a non-neighbor $r\in R_{H}$ and a pair of adjacent vertices $s,k$
where $s\in S_{H}$ and $k\in K_{H}$ such that neither $s$ nor $k$ would be
incident on a fill edge; but then, in $H^{\prime}$, the vertices $u,w,r,s,k$
induce an $F_{4}$ or an $F_{3}$ if $w,r$ have been connected by a fill edge or
not, respectively, which leads to a contradiction. In turn, if $H^{\prime}$
has at least $|K_{H}$ fill edges incident on vertices in $S_{H}\cup K_{H}$
then $H^{\prime}[R_{H}\cup\\{w\\}]$ would be $P_{4}$-sparse using fewer than
$f^{\prime}$ fill edges in contradiction to the minimality of $f^{\prime}$. ∎

######  Lemma 7.

Consider the addition of a tail $uw$ to a _thick_ spider $H=(S_{H}$, $K_{h}$,
$R_{H}$) where $u$ is a vertex of $H$. Then, for the number $f$ of fill edges
(excluding the tail $uw$) in a minimum $P_{4}$-sparse completion of the graph
$H+uw$, it holds:

  1. 1.

if $u\in S_{H}$,

$f\ =\ \begin{cases}\ |K_{H}|-1=2&\mbox{if $|K_{H}|=3$ and
$R_{H}=\emptyset$}\\\ \ |K_{H}|=3&\mbox{if $|K_{H}|=3$ and $|R_{H}|=1$}\\\ \
|K_{H}|+1=4&\mbox{if $|K_{H}|=3$ and $|R_{H}|\geq 2$}\\\ \ |K_{H}|&\mbox{if
$|K_{H}|\geq 4$ and $R_{H}=\emptyset$}\\\ \ |K_{H}|+1&\mbox{if $|K_{H}|\geq 4$
and $|R_{H}|\geq 1$};\end{cases}$

  2. 2.

if $u\in K_{H}$, $f=1$;

  3. 3.

if $u\in R_{H}$, then $f=|K_{H}|+f^{\prime}$ where $f^{\prime}$ is the number
of fill edges (excluding $uw$) in a minimum $P_{4}$-sparse completion of the
graph $H[R_{H}]+uw$.

###### Proof.

1\. Let $v\in K_{H}$ be the non-neighbor of $u$ in $H$. Let us first consider
the case $|K_{H}|=3$. If $|R_{H}|\leq 2$, we can get a $P_{4}$-sparse graph
after having added the fill edges $vu$ and $vw$ (this implies that $v$ becomes
universal in $(V(H)\setminus\\{v\\})\cup\\{w\\}$) and those connecting $u$ to
the vertices in $R_{H}$ if $R_{H}$ is non-empty; then the vertices in
$(V(H)\setminus\\{v\\})\cup\\{w\\}$ induce a thin spider with
$K=(K_{H}\setminus\\{v\\})\cup\\{u\\}$,
$S=(S_{H}\setminus\\{u\\})\cup\\{w\\}$, and $R=R_{H}$, for a total of
$|K_{H}|-1+|R_{H}|$ fill edges (excluding the tail $uw$). If $|R_{H}|\geq 2$,
a $P_{4}$-sparse graph is obtained after in addition to the tail $uw$, we add
the fill edges $vu$, $vw$ (again $v$ is universal in
$(V(H)\setminus\\{v\\})\cup\\{w\\}$), and the fill edges connecting $w$ to the
vertices in $K_{H}\setminus\\{v\\}$ (then the vertices in
$(V(H)\setminus\\{v\\})\cup\\{w\\}$ induce a thin spider with
$K=K_{H}\setminus\\{v\\}$, $S=S_{H}\setminus\\{u\\}$, and
$R=R_{H}\cup\\{u,w\\}$), for a total of $|K_{H}|+1$ fill edges (excluding
$uw$).

Now, consider the case that $|K_{H}|\geq 4$. If $|R_{H}|\leq 1$, we get a
$P_{4}$-sparse graph after having made $u$ universal by connecting it to the
remaining vertices in $S_{H}$ by using $|K_{H}|-1$ fill edges, and adding the
fill edge $uv$, and those connecting $u$ to the vertices in $R_{H}$ if $R_{H}$
is non-empty, for a total of $|K_{H}|+|R_{H}|$ fill edges (excluding $uw$). If
$|R_{H}|\geq 1$, a $P_{4}$-sparse graph is obtained after having made $v$
universal (by adding the fill edges $vu$ and $vw$) and after having connected
$w$ to all vertices in $K_{H}\setminus\\{v\\}$ (then the vertices in
$(V(H)\setminus\\{v\\})\cup\\{w\\}$ induce a thick spider with
$K=K_{H}\setminus\\{v\\}$, $S=S_{H}\setminus\\{u\\}$, and
$R=R_{H}\cup\\{u,w\\}$) for a total of $|K_{H}|+1$ fill edges (excluding
$uw$).

Below we show the minimality of this solution. Recall that $v\in K_{H}$ is the
non-neighbor of $u$ in $H$. We consider each of the five cases.

  * (i)

$|K_{H}|=3$ and $R_{H}=\emptyset$: Suppose, for contradiction, that there is a
$P_{4}$-sparse completion of $H+uw$ with at most $|K_{H}|-2=1$ fill edge
(excluding $uw$). If $v$ is incident on the unique fill edge (which connects
$v$ to $u$ or $w$), then the vertices in $S\cup\\{v,w\\}$ induce an $F_{3}$.
Now suppose that the fill edge is not incident on $v$. Moreover, there exists
at least one vertex $s\in S_{H}\setminus\\{u\\}$ that is not incident on the
fill edge either. Then, the vertices $u,v,w,s,k$ (where $k\in K_{H}$ is the
non-neighbor of $s$ in $H$) induce an $F_{5}$ if $k,w$ are connected by the
fill edge, or an $F_{2}$ otherwise.

  * (ii)

$|K_{H}|=3$ and $|R_{H}|=1$: Let $R_{H}=\\{r\\}$. Suppose, for contradiction,
that there is a $P_{4}$-sparse completion of $H+uw$ with at most $|K_{H}|-1=2$
fill edges (excluding $uw$). We distinguish three cases depending on whether
$v$ is incident on $0$, $1$, or $2$ fill edges:

    * $\bullet$

$v$ is not incident on a fill edge: If there exists a pair $s,k$ of non-
neighbors with $s\in S_{H}\setminus\\{u\\}$ and $k\in K_{H}\setminus\\{v\\}$
such that none of $s,k$ is incident on a fill edge to $u$ or $w$, the vertices
$u,v,w,s,k$ induce an $F_{2}$. Otherwise, since the number of such pairs is
$2$, for each such pair $s,k$, exactly one of $s.k$ is incident on a fill edge
to $u$ or $w$, and no other fill edges exist. If there exists a vertex $k\in
K_{H}\setminus\\{v\\}$ not incident on a fill edge to $w$, the vertices
$u,v,w,k,r$ induce an $F_{5}$, otherwise each of the fill edges connects each
of the vertices in $K_{H}\setminus\\{v\\}$ to $w$, and then $u,v,w,s,k$ (for
any pair $s,k$ of non-neighbors with $s\in S_{H}\setminus\\{u\\}$ and $k\in
K_{H}\setminus\\{v\\}$) induce an $F_{5}$.

    * $\bullet$

$v$ is incident on $1$ fill edge (to $u$ or $w$): Then, there is $1$ more fill
edge; hence, there exist $2$ vertices in the set
$(S_{H}\setminus\\{u\\})\cup\\{r\\}$ that are not incident on a fill edge
connecting them to $u$ or $w$, and let these vertices be $p_{1},p_{2}$. Then,
the vertices $u,v,w,p_{1},p_{2}$ induce an $F_{5}$ if $p_{1},p_{2}$ are
connected by a fill edge or an $F_{3}$ otherwise.

    * $\bullet$

$v$ is incident on $2$ fill edges connecting it to $u$ and $w$: Then, there is
no other fill edge. Then, the vertices $u,w,k,k^{\prime},r$ (where
$\\{k,k^{\prime}\\}=K_{H}\setminus\\{v\\}$) induce an $F_{6}$.

  * (iii)

$|K_{H}|=3$ and $|R_{H}|\geq 2$: Let $r_{1},r_{2}$ be two vertices in $R_{H}$.
Suppose, for contradiction, that there is a $P_{4}$-sparse completion of
$H+uw$ with at most $|K_{H}|=3$ fill edges (excluding $uw$). Again, we
distinguish three cases depending on whether $v$ is incident on $0$, $1$, or
$2$ fill edges:

    * $\bullet$

$v$ is not incident on a fill edge: Consider the case that there exists a
vertex $k\in K_{H}\setminus\\{v\\}$ that is not incident on a fill edge to
$w$. Let $s\in S_{H}$ be the non-neighbor of $k$ in $H$ and
$A=(S_{H}\setminus\\{u,s\\})\cup\\{r_{1},r_{2}\\}$; the set $A$ contains $3$
vertices which are common neighbors of $v,k$. If at least one of these $3$
vertices (say, $p$) is not incident on a fill edge to $u,w$, then the vertices
$u,v,w,k,p$ induce an $F_{5}$, otherwise all $3$ of these vertices are
incident on a fill edge to $u,w$ (then these are all the fill edges) and the
vertices $u,v,w,s,k$ induce an $F_{2}$. On the other hand, if no such vertex
$k$ exists, then both vertices in $K_{H}\setminus\\{v\\}$ are incident on a
fill edge to $w$, accounting for $2$ of the $3$ fill edges; then there exists
a vertex $s^{\prime}\in S_{H}\setminus\\{u\\}$ which is not incident on a fill
edge to $w$, and the vertices $u,v,w,s^{\prime},k^{\prime}$ (where
$k^{\prime}\in K_{H}$ is the non-neighbor of $s^{\prime}$) induce an $F_{5}$.

    * $\bullet$

$v$ is incident on $1$ fill edge (to $u$ or $w$): There are $2$ more fill
edges; hence, there exist $2$ vertices in the set
$(S_{H}\setminus\\{u\\})\cup\\{r_{1},r_{2}\\}$ that are not incident on a fill
edge connecting them to $u$ or $w$, and let these vertices be $p_{1},p_{2}$.
Then, the vertices $u,v,w,p_{1},p_{2}$ induce an $F_{5}$ if $p_{1},p_{2}$ are
connected by a fill edge or an $F_{3}$ otherwise.

    * $\bullet$

$v$ is incident on $2$ fill edges connecting it to $u$ and $w$: Then, there is
$1$ more fill edge; hence, there exists a vertex $k\in K_{H}\setminus\\{v\\}$
that is not incident on the fill edge. Moreover, there exist $2$ vertices in
the set $(S_{H}\setminus\\{u,s\\})\cup\\{r_{1},r_{2}\\}$ that are not incident
on a fill edge connecting them to $u$ or $w$ (where $s\in S_{H}$ is the non-
neighbor of $k$); let these vertices be $p_{1},p_{2}$. Then, the vertices
$u,w,k,p_{1},p_{2}$ induce an $F_{5}$ if $p_{1},p_{2}$ are adjacent or an
$F_{3}$ otherwise.

  * (iv)

$|K_{H}|\geq 4$ and $R_{H}=\emptyset$: Suppose, for contradiction, that there
is a $P_{4}$-sparse completion of $H+uw$ with at most $|K_{H}|-1$ fill edges
(excluding the tail $uw$). Again, we distinguish three cases depending on
whether $v$ is incident on $0$, $1$, or $2$ fill edges:

    * $\bullet$

$v$ is not incident on a fill edge: If there exists a vertex $s\in
S_{H}\setminus\\{u\\}$ not incident on a fill edge to $u$, $w$ or to its non-
neighbor $k\in K_{H}$ in $H$, the vertices $u,v,w,s,k$ induce an $F_{5}$ if
$k,w$ are connected by a fill edge, or an $F_{2}$ otherwise; if all vertices
in $S_{H}\setminus\\{u\\}$ are incident on a fill edge to $u$, $w$, or their
non-neighbor in $K_{H}$, then there are no more fill edges and the vertices
$u,v,w,k,k^{\prime}$ (for any $k,k^{\prime}\in K_{H}\setminus\\{v\\}$) induce
an $F_{6}$.

    * $\bullet$

$v$ is incident on $1$ fill edge (to $u$ or $w$): Then, the remaining fill
edges are at most $|K_{H}|-2$ in total. If there exist two vertices
$s_{1},s_{2}\in S_{H}\setminus\\{u\\}$ not incident on a fill edge to $u$ or
$w$, the vertices $u,v,w,s_{1},s_{2}$ induce an $F_{5}$ or an $F_{3}$
depending on whether $s_{1},s_{2}$ are connected by a fill edge or not. Thus,
there cannot be two such vertices $s_{1},s_{2}$; this implies that the
remaining fill edges are precisely $|K_{H}|-2$, and they connect all but one
vertex in $S_{H}\setminus\\{u\\}$ to $u$ or $w$; let that vertex be $s$. Then,
the vertices $u,v,w,s,k^{\prime}$ (where $k^{\prime}\in K_{H}\setminus\\{v\\}$
is a neighbor of $s$ in $H$) induce an $F_{6}$ or an $F_{1}$ if the fill edge
incident on $v$ connects it to $u$ or $w$ respectively.

    * $\bullet$

$v$ is incident on $2$ fill edges connecting it to $u$ and $w$: Then, the
remaining fill edges are at most $|K_{H}|-3$ in total; hence, there exist two
pairs of non-adjacent vertices $s_{1},k_{1}$ and $s_{2},k_{2}$ with
$s_{1},s_{2}\in S_{H}\setminus\\{u\\}$ and $k_{1},k_{2}\in
K_{H}\setminus\\{v\\}$ such that none of $s_{1},s_{2},k_{1},k_{2}$ is incident
on a fill edge to $u$ or $w$. Let $A=S_{H}\setminus\\{u,s_{1},s_{2}\\}$; the
set $A$ is the set of $|K_{H}|-3$ common neighbors of $k_{1},k_{2}$ in $S_{H}$
other than $u$. If there exists a vertex $s\in A$ not incident on a fill edge
to $u$ or $w$, then the vertices $u,w,k_{1},k_{2},s$ induce an $F_{6}$,
otherwise, the remaining fill edges are precisely $|K_{H}|-3$ and they connect
each of the vertices in $A$ to $u$ or $w$, that is, none of the vertices in
$K_{H}\setminus\\{v\\}$ is incident on a fill edge. Then, the vertices
$u,w,s_{1},s_{2},k$ (where $k$ is any vertex in
$K_{H}\setminus\\{v,k_{1},k_{2}\\}$) induce an $F_{3}$.

  * (v)

$|K_{H}|\geq 4$ and $|R_{H}|\geq 1$: Let $r\in R_{H}$. Suppose, for
contradiction, that there is a $P_{4}$-sparse completion of $H+uw$ with at
most $|K_{H}|$ fill edge (excluding the tail $uw$). Again, w distinguish three
cases depending on whether $v$ is incident on $0$, $1$, or $2$ fill edges:

    * $\bullet$

$v$ is not incident on a fill edge: If there exists a vertex $s\in
S_{H}\setminus\\{u\\}$ not incident on a fill edge to $u$, $w$, or to its non-
neighbor $k\in K_{H}$ in $H$, the vertices $u,v,w,s,k$ induce an $F_{5}$ if
$k,w$ are connected by a fill edge, or an $F_{2}$ otherwise; if all vertices
in $S_{H}\setminus\\{u\\}$ are incident on a fill edge to $u$, $w$, or their
non-neighbor in $K_{H}$, which account for the $|K_{H}|-1$ of the $|K_{H}|$
fill edges, there exist vertices $k,k^{\prime}\in K_{H}\setminus\\{v\\}$ which
are not incident on a fill edge and then the vertices $u,v,w,k,k^{\prime}$
induce an $F_{6}$.

    * $\bullet$

$v$ is incident on $1$ fill edge (to $u$ or $w$): Then, the remaining fill
edges are at most $|K_{H}|-1$ in total. If all vertices in
$K_{H}\setminus\\{v\\}$ are incident on a fill edge to $w$, then no more fill
edges exist and the vertices $u,v,w,s_{1},s_{2}$ (for any $s_{1},s_{2}\in
S_{H}\setminus\\{u\\}$) induce an $F_{3}$. Thus, there exists $k\in
K_{H}\setminus\\{v\\}$ which is not incident on a fill edge to $w$. The number
of common neighbors of $v,k$ in $S_{H}\cup{r}$ is $|K_{H}|-1$. If each of
these vertices is incident on a fill edge to $u$ or $w$, then no more fill
edges exist and the vertices $u,v,w,s,k^{\prime}$ induce an $F_{6}$ or an
$F_{1}$ depending on whether the fill edge incident on $v$ connects it to $u$
or $w$, respectively, where $s\in S_{H}$ is the non-neighbor of $k$ and
$k^{\prime}$ is any vertex in $K_{H}\setminus\\{v,k\\}$; hence, there exists a
common neighbor $p$ not incident on a fill edge to $u$ or $w$ and the vertices
$u,v,w,k,p$ induce an $F_{6}$ or an $F_{1}$ depending on whether the fill edge
incident on $v$ connects it to $u$ or $w$, respectively.

    * $\bullet$

$v$ is incident on $2$ fill edges connecting it to $u$ and $w$: Then, the
remaining fill edges are at most $|K_{H}|-2$ in total; hence, there exists a
pair of non-adjacent vertices $s,k$ (where $s\in S_{H}\setminus\\{u\\}$ and
$k\in K_{H}\setminus\\{v\\}$) which are not incident on a fill edge to $u$ or
$w$. Let $A=(S_{H}\setminus\\{u,s\\})\cup\\{r\\}$; the set $A$ is a set of
$|K_{H}|-1$ neighbors of $k$ other than $u$. Then, there exists a vertex
$p_{1}$ in $A$ which is not incident on a fill edge to $u$ or $w$. If there
exists a second vertex $p_{2}$ in $A$ not incident on a fill edge to $u$ or
$w$, then the vertices $u,w,k,p_{1},p_{2}$ induce an $F_{5}$ if $p_{1},p_{2}$
are connected by a fill edge or an $F_{3}$ otherwise. If each vertex in
$A\setminus\\{p_{1}\\}$ is incident on a fill edge to $u$ or $w$, then the
fill edges incident on these vertices account for the remaining $|K_{H}|-2$
fill edges and the vertices $u,w,s,k_{1},k_{2}$ (for any vertices
$k_{1},k_{2}\in K_{H}\setminus\\{v,k\\}$) induce an $F_{6}$.

Therefore, if we use fewer than the stated number of fill edges, in each case,
the resulting graph contains an induced forbidden subgraph, a contradiction.

2\. Let $v\in S_{H}$ be the non-neighbor of $u$ in $H$. Then, we get a
$P_{4}$-sparse graph by connecting $u$ to $v$; thus, $u$ becomes universal in
$V(H)\cup\\{w\\}$. This is the minimum number of fill edges (excluding the
tail $uw$) that need to be added since for any pair of non-neighbors $s,k$
with $s\in S_{H}\setminus\\{v\\}$ and $k\in K_{H}\setminus\\{u\\}$, the
vertices $u,v,w,s,k$ induce a forbidden subgraph $F_{3}$, a contradiction.

3\. By connecting $w$ to all vertices in $K_{H}$ and then computing a minimum
$P_{4}$-sparse completion of $H[R_{H}\cup\\{w\\}]$, we get a $P_{4}$-sparse
graph and the number of fill edges needed is $|K_{H}|+f^{\prime}$.

To prove the minimality of this number of fill edges, suppose, for
contradiction, that we can get a $P_{4}$-sparse graph from $H+uw$ after having
added at most $|K_{H}|-1$ fill edges incident on vertices in $S_{H}\cup K_{H}$
(excluding the tail $uw$). Then, there exists a pair $s_{1},k_{1}$ of non-
neighbors in $H$ with $s_{1}\in S_{H}$ and $k_{1}\in K_{H}$ none of which is
incident on a fill edge to $u$ or $w$. We distinguish the following two cases
that cover all possibilities.

  * •

_Each of the vertices in $K_{H}\setminus\\{k_{1}\\}$ is incident on a fill
edge to $w$_. These are precisely all the $|K_{H}|-1$ fill edges; hence none
of the vertices in $S_{H}\setminus\\{s_{1}\\}$ is incident on a fill edge.
Then, the vertices $u,w,k_{1},s_{2},s_{3}$ (for any $s_{2},s_{3}\in
S_{H}\setminus\\{s_{1}\\}$) induce an $F_{3}$.

  * •

_There exists at least one vertex in $K_{H}\setminus\\{k_{1}\\}$ that is not
incident on a fill edge to $w$_. Let that vertex be $k_{2}$. Then, if there
exists another vertex $k_{3}\in K_{H}\setminus\\{k_{1},k_{2}\\}$ that is not
incident on a fill edge to $w$ as well, the vertices $u,w,k_{2},k_{3},s_{1}$
induce an $F_{6}$. On the other hand, if each of the vertices in
$K_{H}\setminus\\{k_{1},k_{2}\\}$ is incident on a fill edge to $w$ (which
implies that $k_{3}$ is adjacent to $w$), then these fill edges are
$|K_{H}|-2$ in total, with only $1$ remaining. If the non-neighbor $s_{3}$ of
$k_{3}$ in $S_{H}$ is not incident on a fill edge to $u$ or $w$, then the
vertices $u,w,k_{1},k_{2},s_{3}$ induce an $F_{6}$ whereas if it is adjacent
to $u$ or $w$, then there are no more fill edges. In particular, if $s_{3}$ is
adjacent to $u$, the vertices $u,k_{1},k_{3},s_{1},s_{3}$ induce an $F_{6}$
and if it is adjacent to $w$, the vertices $u,w,k_{2},s_{1},s_{3}$ induce an
$F_{4}$.

In each case, we get a contradiction. Thus every minimum $P_{4}$-sparse
completion of $H+uw$ requires at least $|K_{H}|$ fill edges incident on
vertices of $S_{H}\cup K_{H}$. Now, if there exists a minimum $P_{4}$-sparse
completion $H^{\prime}$ of $H+uw$ having fewer than $|K_{H}|+f^{\prime}$ fill
edges, then the fact that at least $|K_{H}|$ of them are incident on vertices
in $S_{H}\cup K_{H}$ implies that $H^{\prime}[R_{H}\cup\\{w\\}]$ is
$P_{4}$-sparse using fewer than $f^{\prime}$ fill edges in contradiction to
the minimality of $f^{\prime}$. ∎

If the (thin or thick) spider $H$ belongs to a more general $P_{4}$-sparse
graph, then Lemmas 6 and 7 imply the following result.

######  Corollary 1.

Let $u$ be a vertex of a $P_{4}$-sparse graph to which we add the tail $uw$.
Let $t_{0}\cdots t_{h}u$ be the path in the $P_{4}$-sparse tree of $G$ from
the the root $t_{0}$ to the leaf for $u$ and let $V_{0},\ldots,V_{h}$ be the
corresponding vertex sets as mentioned before. Then, if the parent $t_{h}$ of
$u$ is a $2$-node corresponding to a spider $H$, the number of fill edges
needed for a minimum $P_{4}$-sparse completion of the graph $G+uw$ (excluding
the tail $uw$) does not exceed the minimum between

  * (i)

the minimum number given by Lemmas 6 and 7 (if $H$ is thin or thick,
respectively) augmented by $|N_{G}(u)\cap(V_{0}\cup\cdots\cup V_{h-1})|$ and

  * (ii)

$\min_{t_{i}=1\text{- or }2\text{-node}}\\{\,|N_{G}(u)\cap(V_{0}\cup\ldots\cup
V_{i-1})|+|(V_{i}\cup\ldots\cup V_{h})\setminus N_{G}(u)|\,\\}$.

Case (i) of Corollary 1 corresponds to doing a minimum $P_{4}$-completion of
the graph $H+uw$ and not changing the rest of the $P_{4}$-sparse tree $T_{G}$
of $G$ whereas Case (ii) corresponds to making $u$ universal in $H$ and then
trying Formation $2$ above each $1$-node or $2$-node in the path $t_{0}\cdots
t_{h}$ of $T_{G}$.

###  5.2 The Algorithm

Recall that $t_{0}t_{1}\cdots t_{h}u$ is the path in the $P_{4}$-sparse tree
$T_{G}$ of $G$ from the root $t_{0}$ to the leaf for $u$, and $V_{i}$ ($0\leq
i<h$) is the set of vertices associated with the leaves of the subtrees rooted
at the children of $t_{i}$ except for $t_{i+1}$ and $V_{h}$ is the set of
vertices associated with the leaves of the subtrees rooted at the children of
$t_{h}$ except for the leaf corresponding to $u$. See Figure 5.

Next we prove the conditions under which a minimum $P_{4}$-sparse completion
of the graph $G+uw$ uses fewer fill edges than when using Formation $1$ or
$2$.

######  Lemma 8.

There exists a minimum $P_{4}$-sparse completion $G_{OPT}$ of the graph $G+uw$
which uses fewer fill edges than when using Formation $1$ or $2$ if and only
if $uw$ is a wing of a $P_{4}$ in $G_{OPT}$ which implies that (i) either $u$
is a vertex of a spider in $G$ (Lemmas 6 and 7 apply) (ii) or there exists $j$
($0\leq j<h$) such that $t_{j}$ is a $1$-node, $t_{j+1}$ is a $0$-node, and
there exist vertices $a,b$ such that $a\in V_{j}$ is universal in $G[V_{j}]$
and $b\in V_{j+1}$ is isolated in $G[V_{j+1}]$.
Then, in $G_{OPT}$, the vertices $u,w,a,b$ induce a $P_{4}$ in a spider
$(S,K,R)$ with $S=\\{w,b\\}$, $K=\\{u,a\\}$ and
$R=(V_{j+1}\setminus\\{b\\})\cup V_{j+2}\cup\cdots\cup V_{h}$.

###### Proof.

If Formation $1$ or Formation $2$ is not to be used then Lemma 5 implies that
in $G_{OPT}$, $uw$ is the wing of a $P_{4}$. If $u$ is a vertex of a spider,
then Lemmas 6 and 7 apply. So, in the following, assume that $u$ is not a
vertex of a spider.

For the tail $uw$ to be the wing of a $P_{4}$ in $G_{OPT}$, we can show that
there exist vertices $x,y$ such that $uxy$ is a $P_{3}$ in the graph $G$: if
$u,x,y$ do not all belong to the same connected component of $G$, then we
could add the tail $uw$ to the connected component of $G$ to which $u$
belongs, thus using fewer fill edges than in $G_{OPT}$, a contradiction; if
$u,x,y$ belong to the same connected component of $G$ but do not form a
$P_{3}$, then because $u,y$ are not adjacent in $G_{OPT}$ and thus neither in
$G$, $u,y$ are at distance $2$ in $G$ and there exists a $P_{3}$ $uay$ in $G$
(note that $u,y$ cannot be at distance $\geq 4$ in $G$ since then $G$ would
contain an induced $P_{5}=F_{2}$, and they cannot be at distance $3$ either
since then there exists a $P_{4}$ $uaby$ in $G$ and $u$ would be a vertex of a
spider in $G$).

Therefore, in the following, consider that the minimum $P_{4}$-sparse
completion $G_{OPT}$ of $G+uw$ contains an induced $P_{4}$ $wuab$ such that
the graph $G$ contains the induced $P_{3}$ $uab$. So, since $u,b$ are not
adjacent in $G_{OPT}$, then they are not adjacent in $G$ either, and thus
their least common ancestor $t_{k}$ in the $P_{4}$-sparse tree $T_{G}$ of $G$
is a $0$-node; it cannot be a $2$-node since then $u$ would be a vertex of a
spider. Moreover, $a$ is a common neighbor of both $u,b$ and thus the least
common ancestor $t_{j}$ of $a,u$ in $T_{G}$ is a $1$\- or a $2$-node (in the
latter case, $a$ is a vertex of the clique of the spider) and $j<k$.

Let us now try forming the $P_{4}$ $wuab$, which clearly will belong to a
spider, say $W=(S_{W},K_{W},R_{W})$. We show that $|S_{W}|=|K_{W}|=2$. First,
note that the edge $ab$ cannot belong to a spider in $G$, since then $u$ would
belong to that spider as well (note that the vertices of $G$ not belonging to
a spider are either adjacent to all vertices of the spider or to none of
them), So, suppose for contradiction that the spider $W$ has
$|S_{W}|=|K_{W}|\geq 3$ and let $w,b,s\in S_{W}$ and $u,a,k\in K_{W}$ with the
corresponding $S$-$K$ pairs being $w$ and $u$, $b$ and $a$, and $s$ and $k$.
The spider $W$ can be thin or thick.

  * •

_The spider $W$ is thin_. Then, $ba\in E(G)$ otherwise the removal of $ba$
would produce a $P_{4}$-sparse graph with fewer fill edges ($b$ is isolated in
$G[V(W)]$), a contradiction; similarly, $sk\in E(G)$. Moreover, $ak\in E(G)$:
as above, if $a,k$ do not belong to the same connected component of the
induced subgraph $G[V(W)]$, then by adding the tail $uw$ to the connected
component of $G[V(W)]$ to which $u$ belongs would result into fewer fill
edges; if $a,k$ belong to the same connected component of $G[V(W)]$ then there
exists a chordless path $\rho$ connecting them in the subgraph $G[K_{W}\cup
R_{W}]$ and the vertices in $V(\rho)\cup\\{b,s\\}$ induce a $P_{\ell}$ with
$\ell\geq 5$, in contradiction to the $P_{4}$-sparseness of $G$. But then, $G$
contains the $P_{4}$ $baks$ and $ab$ belongs to a spider.

  * •

_The spider $W$ is thick_. Then, $w\in S_{W}$ is incident on the tail $uw$ and
$|K_{W}|-2\geq 1$ fill edges. Since we can make $u$ universal in
$G[V(W)\setminus\\{w\\}]$ by using a single fill edge and then use Formation
$2$, it is clear that building the spider $W$ does not result into fewer fill
edges.

Thus, $G_{OPT}$ with a spider $W$ with $|K_{W}|\geq 3$ has no fewer fill edges
than if we use Formation $2$. Therefore, the $P_{4}$ $wuab$ belongs to a
spider with clique size equal to $2$, which thus is thin. Then, Property P1 in
Lemma 4 implies that $w$, $u$, and $a$ are adjacent to all the neighbors of
$b$ except for $a$ in $G_{OPT}$ and thus at least to the neighbors of $b$ in
$G$; thus, in $G_{OPT}$,

  * •

fill edges connect vertex $w$ to the vertices in $((V_{0}\cup\cdots\cup
V_{k-1})\setminus\\{a\\})\cap N_{G}(b)=[(V_{0}\cup\cdots\cup
V_{k-1})\setminus\\{a\\}]\cap N_{G}(u)$;

  * •

vertex $u$ and $w$ are adjacent to all neighbors of $b$ in $V_{k}$, that is,
to the vertices in $(V_{k}\cap N_{G}(b))\setminus N_{G}(u)$;

  * •

vertex $a$ is adjacent to all the vertices in $(V_{j}\cap N_{G}(b))$ and thus
fill edges connect $a$ to all vertices in $(V_{j}\cap N_{G}(b))\setminus
N_{G}[a]$ $=(V_{j}\cap N_{G}(u))\setminus N_{G}[a]$.

Additionally, Property P2 in Lemma 4 implies that because $a$ is adjacent to
all the vertices in $V_{j+1}\cup\cdots\cup V_{h}$ and to the vertices in
$V_{j}\cap N_{G}(a)$ in $G_{OPT}$ (because it is adjacent to them in $G$),
then so must be vertex $u$ in $G_{OPT}$; thus, in $G_{OPT}$, fill edges
connect $u$ to all the vertices in $(V_{j+1}\cup\cdots\cup V_{h})\setminus
N_{G}(u)$ and the vertices in $(V_{j}\cap N_{G}(a))\setminus N_{G}(u)$ (the
set $(V_{j}\cap N_{G}(a))\setminus N_{G}(u)$ is non-empty if and only if
$t_{j}$ is a $2$-node).

Now, let us consider using Formation $2$ right below node $t_{j}$ in the
$P_{4}$-sparse tree $T_{G}$ of $G$; then, the number of fill edges is
$|(V_{j+1}\cup\cdots\cup V_{h})\setminus N_{G}(u)|+|(V_{0}\cup\cdots\cup
V_{j})\cap N_{G}(u)|$; the former term corresponds to fill edges incident on
$u$, the latter to fill edges incident on $w$. Then, because $j<k$ and
$|((V_{0}\cup\cdots\cup V_{k-1})\setminus\\{a\\})\cap
N_{G}(u)|=|(V_{0}\cup\cdots\cup V_{k-1})\cap N_{G}(u)|-1$, the only
possibility for $G_{OPT}$ to use fewer fill edges than using Formation $2$
after node $t_{j}$ requires that

  1. 1.

$k=j+1$;

  2. 2.

$(V_{j}\cap N_{G}(u))\setminus N_{G}[a]=\emptyset$;

  3. 3.

$(V_{k}\cap N_{G}(b))\setminus N_{G}(u)=\emptyset$ which implies that $b$ is
isolated in $G[V_{k}]$;

  4. 4.

$(V_{j}\cap N_{G}(a))\setminus N_{G}(u)=\emptyset$ which implies that $t_{j}$
is a $1$-node.

Requirement $4$ implies that $V_{j}\cap N_{G}(u)=V_{j}$ which together with
Requirement $2$ imply that $N_{G}[a]=V_{j}$, that is, $a$ is universal in
$G[V_{j}]$, and we have the second case in the statement of the lemma. ∎

Now we are ready to describe our algorithm for counting the number of fill
edges in a minimum $P_{4}$-sparse completion of the graph $G+uw$.

Algorithm $P_{4}$-sparse-Tail-Addition
_Input_ : a $P_{4}$-sparse graph $G$, a vertex $u\in V(G)$, and a tail $uw$ to
be added to $G$.
_Output_ : the minimum number of fill edges (excluding the tail $uw$) needed
in a
_Output_ : $P_{4}$-sparse completion of the graph $G+uw$.

if $|V(G)|=1$ then $\\{$$V(G)=\\{u\\}\Longrightarrow$ the graph $G+uw$ is
$P_{4}$-sparse$\\}$
xx return(0);

compute the path $t_{0}t_{1}...t_{h}$ ($h\geq 1$) from the root $t_{0}$ of the
$P_{4}$-sparse tree of $G$ to the parent-node $t_{h}$ of the leaf
corresponding to $u$;
compute the sets of vertices $V_{i}$. $0\leq i\leq h$ (see Figure 5);

$min\leftarrow|N_{G}(u)|$; $\\{$corresponds to Formation $1$$\\}$

$\\{$check for Formation $2$ (Lemma 5(iii) and Case (ii) of Corollary 1)$\\}$
for each $t_{i}$ ($i=0,1,\ldots,h$) that is a $1$\- or a $2$-node do
xx $\ell\leftarrow|N_{G}(u)\cap(V_{0}\cup\cdots\cup
V_{i-1})|+|(V_{i}\cup\cdots\cup V_{h})\setminus N_{G}(u)|$;
xx update $min$ if $\ell<min$;

$\\{$check for new $P_{4}$ formation (Lemma 8)$\\}$
for each $i=0,1,\ldots,h-1$ such that $t_{i}$ is a $1$-node and $t_{i+1}$ is a
$0$-node do
xx if there exist vertex $a\in V_{i}$ such that $a$ is universal in $V_{i}$
and
xx if there exist vertex $b\in V_{i+1}$ such that $b$ has no neighbors in
$V_{i+1}$ then
xx $\ell\leftarrow|N_{G}(u)\cap(V_{0}\cup\cdots\cup
V_{i-1})|+|V_{i}\setminus\\{a\\}|+|V_{i+1}\setminus\\{b\\}|+\\\
\phantom{xxxxxxxxxxxxxxxxx}\phantom{xxxxxxxxxxxxxxxxx}|(V_{i+2}\cup\cdots\cup
V_{h})\setminus N_{G}(u)|$;
xx update $min$ if $\ell<min$;

$\\{$check the cases if $t_{h}$ is a $2$-node and apply case (i) of Corollary
1$\\}$
if $t_{h}$ is a $2$-node then
xx $\ell\leftarrow$ number of fill edges according to the cases of Lemmas 6 or
7;
xx $\ell\leftarrow\ell+|N_{G}(u)\cap(V_{0}\cup\cdots\cup V_{h-1})|$; $\\{$Case
(i) of Corollary 1$\\}$
xx update $min$ if $\ell<min$;
return($min$);

Algorithm $P_{4}$-sparse-Tail-Addition can be easily augmented to return a
minimum cardinality set of fill edges. The correctness of the algorithm
follows from Lemmas 5, 6, 7, 8, and Corollary 1. Let $G$ be the given graph
and let $n$ be the number of its vertices. If the $P_{4}$-sparse tree $T_{G}$
of $G$ is given, an $O(n)$-time traversal of the tree enables us to compute
the path $t_{0}t_{1}\cdots t_{h}u$ and the number of neighbors and non-
neighbors of $u$ in each of the sets $V_{0},\ldots,V_{h}$; additionally, the
height of $T_{G}$ is $O(n)$ and thus $h=O(n)$. Since the conditions of Lemmas
6 and 7 can be checked in $O(1)$-time, the entire algorithm runs in $O(n)$
time.

######  Theorem 5.1.

Let $G$ be a $P_{4}$-sparse graph on $n$ vertices and let $uw$ be tail
attached at node $u$ of $G$. If the $P_{4}$-sparse tree of $G$ is given,
Algorithm $P_{4}$-sparse-Tail-Addition computes the minimum number of edges to
be added to $G+uw$ so that the resulting graph is $P_{4}$-sparse in $O(n)$
time.

If the $P_{4}$-sparse tree $T_{G}$ of $G$ is not given, then it can be
computed in $O(n+m)$ time where $m$ is the number of edges of $G$ [14], and
the entire algorithm takes $O(n+m)$ time.

## References

  * [1] Brandstädt, A., Le, V.B., Spinrad, J.: Graph Classes – a Survey. SIAM Monographs in Discrete Mathematics and Applications, SIAM, Philadelphia (1999)
  * [2] Burzyn, P., Bonomo, F., Durán, G.: NP-completeness results for edge modification problems. Discrete Apll. Math. 154, 1824–1844 (2006)
  * [3] Chvátal, V., Hammer, P.L.: Set-packing and threshold graphs, Research Report CORR 73-21, University of Warerloo, 1973.
  * [4] Corneil, D.G, Lerches, H., Burlingham, L.: Complement reducible graphs, Discrete Appl. Math. 3 163–174 (1981).
  * [5] Corneil, D.G., Perl, Y., Stewart, L.K.: A linear recognition algorithm for cographs, SIAM J. Comput. 14 926–934 (1985).
  * [6] Golumbic, M.C.: Trivially perfect graphs, Discrete Math. 24 105–107 (1978).
  * [7] Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs, Academic Press, New York, 1980.
  * [8] El-Mallah, E., Colbourn, C.: The complexity of some edge deletion problems. IEEE Trans. Circuits Systems 35, 354–362
  * [9] Goldberg, P.W., Golumbic, M.C., Kaplan, H., Shamir, R.: Four strikes against physical mapping of DNA. J. Comput. Bio. 2(1), 139–152 (1995)
  * [10] Heggernes, P., Mancini, F.: Dynamically maintaining split graphs, Discrete Appl. Math. 157, 2047–2069 (2009)
  * [11] Hell, P., Shamir, R., Sharan, R.: A fully dynamic algorithm for recognizing and representing proper interval graphs. SIAM J. Comput. 31, 289–305 (2002)
  * [12] Hoáng, C.: Perfect graphs. Ph.D. Thesis, McGill University, Montreal, Canada (1985)
  * [13] Ibarra, L.: Fully dynamic algorithms for chordal graphs and split graphs. ACM Trans. Algorithms 4, Article 40 (2008)
  * [14] Jamison, B., Olariu, S.: Recognizing $P_{4}$-sparse graphs in linear time. SIAM J. Comput. 21, 381–-406 (1992)
  * [15] Jamison, B., Olariu, S.: A tree representation for $P_{4}$-sparse graphs. Discrete Appl. Math. 35, 115–-129 (1992)
  * [16] Kashiwabara, T., Fujisawa, T.: An NP-complete problem on interval graphs. In: IEEE Symp. of Circuits and Systems, pp. 82–83 (1979)
  * [17] Kano, M., Nikolopoulos, S.D.: On the structure of A-free graphs. Part II, TR-25-99, Department of Computer Science, University of Ioannina, 1999.
  * [18] Ma, S., Wallis, W.D., Wu, J.: Optimization problems on quasi-threshold graphs, J. Comb. Inform. System Sci. 14 105–110 (1989).
  * [19] Natanzon, A., Shamir, R., Sharan, R.: Complexity classification of some edge modification problems. Discrete Appl. Math. 113, 109–128 (2001)
  * [20] Nikolopoulos, S.D.: Recognizing cographs and threshold graphs through a classification of their edges. Information Processing Letters 74.3-4 (2000): 129-139.
  * [21] Nikolopoulos, S.D.: Parallel algorithms for Hamiltonian problems on quasi-threshold graphs. Parallel and Distributed Computing 64, 48–67 (2004).
  * [22] Nikolopoulos, S.D., Palios, L.: Adding an Edge in a Cograph. In: Kratsch D. (ed.) WG 2005, LNCS, vol. 3787, pp. 214–226, Springer (2005).
https://doi.org/10.1007/11604686_19

  * [23] Nikolopoulos, S.D., Palios, L., Papadopoulos, C.: A fully-dynamic algorithm for the recognition of $P_{4}$-sparse graphs. Theor. Comp. Science 439, 41-57 (2012).
  * [24] Nikolopoulos, S.D., Papadopoulos, C.: The number of spanning trees in K n-complements of quasi-threshold graphs. Graphs and Combinatorics 20.3: 383-397 (2004).
  * [25] Rose, D.J.: A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equation. In: Read, R.C.(ed.) Graph Theory and Computing, pp. 183–217. Academic Press, New York (1972)
  * [26] Shamir, R., Sharan, R.: A fully dynamic algorithm for modular decomposition and recognition of cographs. Discrete Appl. Math. 136, 329–340 (2004)
  * [27] Wolk, E.S.: The comparability graph of a tree. Proc. Amer. Math. Soc. 3 789–795 (1962) .
  * [28] Wolk, E.S.: A note of the comparability graph of a tree. Proc.Amer. Math. Soc. 16 17–20 (1965).
  * [29] Veldman, H.J.: A result on Hamiltonian line graphs involving restrictions on induced subgraphs. J. Graph Theory 12 413–420 (1988).
  * [30] Yannakakis, M.: Computing the minimum fill-in is NP-complete. SIAM J. Alg. Disc. Meth. 2, 77–79 (1981)