TY - JOUR
T1 - On the proper interval completion problem within some chordal subclasses
AU - Dross, François
AU - Hilaire, Claire
AU - Koch, Ivo
AU - Leoni, Valeria
AU - Pardal, Nina
AU - Pujato, María Inés Lopez
AU - Santos, Vinicius Fernandes Dos
N1 - Funding Information:
Partially supported by Programa Regional MATHAMSUD MATH190013, by CNPq grants 311679/2018-8, 312069/2021-9 and 406036/2021-7, by FAPEMIG grant APQ-01707-21, by Argentina PIP 2021-2023 20020190200124BA, by Argentina UBACyT 20020170100495BA, by DFG grant VI 1045/1-1, by the Slovenian Research and Innovation Agency (research project J1-4008).
Publisher Copyright:
© 2024 The Author(s)
PY - 2025/1/1
Y1 - 2025/1/1
N2 - 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.
AB - 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.
KW - Caterpillar
KW - Proper interval completion
KW - Quasi-threshold graph
KW - Split graph
KW - Threshold graph
UR - http://www.scopus.com/inward/record.url?scp=85205714602&partnerID=8YFLogxK
U2 - 10.1016/j.disc.2024.114274
DO - 10.1016/j.disc.2024.114274
M3 - Article
VL - 348
JO - Discrete Mathematics
JF - Discrete Mathematics
SN - 0012-365X
IS - 1
M1 - 114274
ER -