  The minimum completion (fill-in) problem is defined as follows: Given a graph
family $\mathcal{F}$ (more generally, a property $\Pi$) and a graph $G$, the
completion problem asks for the minimum number of non-edges needed to be added
to $G$ so that the resulting graph belongs to the graph family $\mathcal{F}$
(or has property $\Pi$). This problem is NP-complete for many subclasses of
perfect graphs and polynomial solutions are available only for minimal
completion sets. We study the minimum completion problem of a $P_4$-sparse
graph $G$ with an added edge. For any optimal solution of the problem, we prove
that there is an optimal solution whose form is of one of a small number of
possibilities. This along with the solution of the problem when the added edge
connects two non-adjacent vertices of a spider or connects two vertices in
different connected components of the graph enables us to present a
polynomial-time algorithm for the problem.
