On the proper interval completion problem within some chordal subclasses
| Autor: | Dross, François, Hilaire, Claire, Koch, Ivo, Leoni, Valeria, Pardal, Nina, Pujato, María Inés Lopez, Santos, Vinicius Fernandes dos |
|---|---|
| Rok vydání: | 2021 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | Given a property (graph class) $\Pi$, a graph $G$, and an integer $k$, the \emph{$\Pi$-completion} problem consists in deciding whether we can turn $G$ into a graph with the property $\Pi$ by adding at most $k$ edges to $G$. The $\Pi$-completion problem is known to be NP-hard for general graphs when $\Pi$ is the property of being a proper interval graph (PIG). In this work, we study the PIG-completion problem %when $\Pi$ is the class of proper interval graphs (PIG) 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. Comment: 15 pages, 4 figures |
| Databáze: | arXiv |
| Externí odkaz: |
|