Adding an Edge in a P_4-sparse Graph
share
The minimum completion (fill-in) problem is defined as follows: Given a graph family ℱ (more generally, a property Π) 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 ℱ (or has property Π). 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.
READ FULL TEXT