On the proper interval completion problem within some chordal subclasses

Abstract

Given a property (graph class) , a graph G, and an integer k, the -completion problem consists of deciding whether we can turn G into a graph with the property by adding at most k edges to G. The -completion problem is known to be NP-hard for general graphs when is the property of being a proper interval graph (PIG). In this work, we study the PIG-completion problem within different subclasses of chordal graphs. We show that the problem remains NP-complete even when restricted to split graphs. We then turn our attention to positive results and present polynomial time algorithms to solve the PIGcompletion problem when the input is restricted to caterpillar and threshold graphs. We also present an efficient algorithm for the minimum co-bipartite-completion for quasithreshold graphs, which provides a lower bound for the PIG-completion problem within this graph class.