20.500.12556/RUP-21529 On the proper interval completion problem within some chordal subclasses 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. proper interval completion split graph threshold graph quasi-threshold graph caterpillar pravilno dokončanje intervala razdeljeni graf graf praga graf kvazipraga caterpillar true false false Angleški jezik Slovenski jezik Članek v reviji 2025-08-06 12:48:10 2025-08-06 12:48:11 2025-08-07 03:04:45 0000-00-00 00:00:00 2025 0 0 str. 1-15 iss. 1, [article no.] 114274 Vol. 348 Jan. 2025 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 2024-10-07 519.17 0012-365X 10.1016/j.disc.2024.114274 218515203 RAZ_Dross_Francois_2025.pdf RAZ_Dross_Francois_2025.pdf 1 5C5BFD7A9C8D8F83829B6108263FAF36 a91075848ffe6f39b8203892e57a1bf8e59044b6d75f4d28145b12dda6192a07 f9b58390-72b2-11f0-8f0b-005056ac49c0 https://repozitorij.upr.si/Dokument.php?lang=slv&id=31307 https://doi.org/10.1016/j.disc.2024.114274 1 dd59ecc1-72b2-11f0-8f0b-005056ac49c0 https://repozitorij.upr.si/Dokument.php?lang=slv&id=31306 Fakulteta za matematiko, naravoslovje in informacijske tehnologije 0 0 0