On the proper interval completion problem within some chordal subclasses

François Dross, Claire Hilaire, Ivo Koch, Valeria Leoni, Nina Pardal, María Inés Lopez Pujato, Vinicius Fernandes Dos Santos

Research output: Contribution to journalArticlepeer-review

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 PIG-completion problem when the input is restricted to caterpillar and threshold graphs. We also present an efficient algorithm for the minimum co-bipartite-completion for quasi-threshold graphs, which provides a lower bound for the PIG-completion problem within this graph class.

Original languageEnglish
Article number114274
Number of pages15
JournalDiscrete Mathematics
Volume348
Issue number1
Early online date7 Oct 2024
DOIs
Publication statusPublished - 1 Jan 2025
Externally publishedYes

Cite this