Minimum completions from interval to proper interval graphs

NINA PARDAL

Workshop; STALGRAPH Workshop; 2020

Universidad de Chile

A graph class Π is a family of graphs having the property Π, for example, Π can be the property of being chordal, planar, perfect, etc. A Π-completion of a graph G = (V, E) is a supergraph H = (V,E ∪F) such that H belongs to Π and E ∩F = ∅. In other words, we want to find a set of edges F such that, when added to G, the resulting graph belongs to the class Π. A Π-completion is minimum if for any set of edges F ′ such that H′ = (V, E ∪ F ′) belongs to Π, then |F ′| ≥ |F |. A Π-completion is minimal if for any proper subset F ′ ⊂ F the supergraph H′ = (V, E ∪ F ′) does not belong to Π.The problem of calculating a minimum completion from an arbitrary graph to a specific graph class has been widely studied. Unfortunately, it has been shown to be NP-hard to compute in some target graph classes such as cographs, chordal graphs and interval graphs, to name a few. For this reason, current research on this topic is focused on finding minimal completions of arbitrary graphs to specific graph classes in the most efficient way possible from the computational point of view.We want to study the problem of finding a minimum and a minimal completion to proper interval graphs when the input graph is already interval. More precisely, we would like to determine the complexity of finding a minimum completion in this particular case and to structurally characterize both the minimum and minimal solutions for this problem.We propose the following conjecture: the minimum version of this problem is NP- complete.