A matching-cut of a graph is an edge cut that is a matching. The problem Matching-Cut is that of recognizing graphs with a matching-cut and is NP-complete, even if the graph belongs to one of a number of classes. We initiate the study of Matching-Cut for graphs without a fixed path as an induced subgraph. We show that Matching-Cut is in P for $P_5$-free graphs, but that there exists an integer $t > 0$ for which it is NP-complete for $P_{t}$-free graphs.


翻译:图形的匹配剪切是一个匹配的边端剪切。 匹配剪切的问题是识别带有匹配剪切的图形, 并且是NP- 完整, 即使该图形属于若干类中的一个。 我们开始研究没有固定路径的图形匹配剪切作为诱导子图。 我们显示匹配剪切在 P 中, $P_ 5$- free 图形, 但是存在一个整数 $t > 0$, 而对于 $P_ t} $free 图表来说, 它是 NP- complete 。

0
下载
关闭预览

相关内容

【干货书】开放数据结构,Open Data Structures,337页pdf
专知会员服务
16+阅读 · 2021年9月17日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
专知会员服务
115+阅读 · 2019年12月24日
【新书】Python编程基础,669页pdf
专知会员服务
193+阅读 · 2019年10月10日
TensorFlow 2.0 Datasets 数据集载入
TensorFlow
6+阅读 · 2020年1月31日
TensorFlow 2.0新特性之Ragged Tensor
深度学习每日摘要
18+阅读 · 2019年4月5日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
【 关关的刷题日记47】Leetcode 38. Count and Say
【LeetCode 500】关关的刷题日记27 Keyboard Row
专知
3+阅读 · 2017年11月5日
Arxiv
0+阅读 · 2022年1月28日
Arxiv
0+阅读 · 2022年1月27日
Arxiv
3+阅读 · 2018年10月18日
VIP会员
相关资讯
TensorFlow 2.0 Datasets 数据集载入
TensorFlow
6+阅读 · 2020年1月31日
TensorFlow 2.0新特性之Ragged Tensor
深度学习每日摘要
18+阅读 · 2019年4月5日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
【 关关的刷题日记47】Leetcode 38. Count and Say
【LeetCode 500】关关的刷题日记27 Keyboard Row
专知
3+阅读 · 2017年11月5日
Top
微信扫码咨询专知VIP会员