Structural characterization of minimal and minimum completions

NINA PARDAL; GUILLERMO A. DURÁN; MARIO VALENCIA-PABON

La Plata

Workshop; Latin-American Workshop on Clique in Graphs 2016; 2016

UNLP

A Π-completion H = (V, E ∪ F) of a graph G = (V, E) is called minimal if for every proper subset F´ of F the graph H´ = (V, E ∪F´) does not belongto the class Π, and its minimum if for every Π-completion H´ = (V, E ∪ F´) the size of F is smaller than or equal to the size of F´. It is clear that every minimum Π-completion is minimal, but the reciprocal is not true.The problem of calculating a minimum completion from an arbitrarygraph to a specific one is very important and quite studied since it has applications in various areas like molecular biology, computational algebra, and more specifically in areas that involve modelling based on graphs where the missing edges represent lack of data, such as in clustering data problems.Unfortunately, minimum arbitrary graph completions to most graph classesare NP-hard problems. For this reason, current investigations are focusedon finding minimal completions for arbitrary graphs to specific classes in the most efficient possible way from the computational point of view.In this work, we find a structural characterization for minimal completions in the case where the initial graph G belongs to the class of interval graphs, and the completion is a graph H in the class of proper interval graphs. This characterization allowed us to find a polynomial time recognition algorithm for minimal completions in this particular case.