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.


翻译:根据一个属性(graph class) $\ pi$, 一个图形 G$, 和一个整数 美元, 问题在于决定我们是否能够将$G$转换成一个含有$\ Pi$的图形, 将最多以美元表示的边缘加到$G$。 当$\ Pi$是适当的间隔图( PIG)的属性时, 已知通用图的完成问题为 NP- hard 。 在这项工作中, 当$\ Pi$是不同相形图分类中适当的间隔图( PIG) 的类别时, 我们研究 PIG- 完成问题% 。 我们显示, 问题仍然是NP- 完整的, 即使限于以美元表示的分形图。 当输入限于毛虫和临界图时, 我们就会将注意力转向正结果, 并提出聚度时间算法来解决 PIG- 补全问题。 我们还为准线图( PIG) 的最低双部分补全率算法 。

0
下载
关闭预览

相关内容

【CVPR2021】自监督几何感知
专知会员服务
45+阅读 · 2021年3月6日
「深度图像检索: 2012到2020」大综述论文,21页pdf
专知会员服务
41+阅读 · 2021年1月30日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
最新BERT相关论文清单,BERT-related Papers
专知会员服务
52+阅读 · 2019年9月29日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
【 关关的刷题日记47】Leetcode 38. Count and Say
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
已删除
将门创投
9+阅读 · 2017年10月17日
From Softmax to Sparsemax-ICML16(1)
KingsGarden
72+阅读 · 2016年11月26日
Arxiv
0+阅读 · 2021年12月9日
Arxiv
0+阅读 · 2021年12月9日
Arxiv
0+阅读 · 2021年12月8日
Arxiv
0+阅读 · 2021年12月5日
VIP会员
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
【 关关的刷题日记47】Leetcode 38. Count and Say
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
已删除
将门创投
9+阅读 · 2017年10月17日
From Softmax to Sparsemax-ICML16(1)
KingsGarden
72+阅读 · 2016年11月26日
Top
微信扫码咨询专知VIP会员