会员服务
图 · 边 · 结点 · 离散数学 · 算法与数据结构 ·
2022 年 11 月 22 日
Edge Multiway Cut and Node Multiway Cut are NP-complete on subcubic graphs
翻译：边缘多路切断和节点多路切断在子立方图上为 NP 完成
Matthew Johnson,Barnaby Martin,Siani Smith,Sukanya Pandey,Daniel Paulusma,Erik Jan van Leeuwen
Matthew Johnson,Barnaby Martin,Siani Smith,Sukanya Pandey,Daniel Paulusma,Erik Jan van Leeuwen

We show that Edge Multiway Cut (also called Multiterminal Cut) and Node Multiway Cut are NP-complete on graphs of maximum degree $3$ (also known as subcubic graphs). This improves on a previous degree bound of $11$. Our NP-completeness result holds even for subcubic graphs that are planar.


翻译：我们显示,边缘多路切断(也称为多端断线切断)和节点多路切断在最高度3美元的图表(也称为子立方图)上是NP的完整。 这在先前的11美元绑定度上有所改进。 我们的NP完整性结果甚至维持在平面的子立方图上。
0
下载
关闭预览

相关内容

高效可扩展图神经网络的研究进展，Recent Advances in Efficient and Scalable Graph Neural Networks
高效可扩展图神经网络的研究进展，Recent Advances in Efficient and Scalable Graph Neural Networks
专知会员服务
75+阅读 · 2022年3月15日
71页PDF，Intro to the Metaverse（元宇宙概念发展透析），Newzoo Trend Report 2021
71页PDF，Intro to the Metaverse（元宇宙概念发展透析），Newzoo Trend Report 2021
专知会员服务
21+阅读 · 2022年2月19日
ICLR 2021杰出论文奖出炉，8篇论文上榜！
专知会员服务
25+阅读 · 2021年4月2日
一份简单《图神经网络》教程，28页ppt
一份简单《图神经网络》教程，28页ppt
专知会员服务
123+阅读 · 2020年8月2日
【新书】人工智能Python代码，227页pdf，Python code for Artificial Intelligence: Foundations of Computational Agents
【新书】人工智能Python代码，227页pdf，Python code for Artificial Intelligence: Foundations of Computational Agents
专知会员服务
99+阅读 · 2020年6月21日
50+篇《神经架构搜索NAS》2020论文合集
专知会员服务
60+阅读 · 2020年3月19日
100+篇《自监督学习(Self-Supervised Learning)》论文最新合集
100+篇《自监督学习(Self-Supervised Learning)》论文最新合集
专知会员服务
164+阅读 · 2020年3月18日
【新书】数字图像(影像)处理手第二版，2176pdf，Mathematical Methods in Imaging
【新书】数字图像(影像)处理手第二版，2176pdf，Mathematical Methods in Imaging
专知会员服务
88+阅读 · 2020年2月12日
【论文推荐】几何图形卷积网络，GEOM-GCN: GEOMETRIC GRAPH CONVOLUTIONAL NETWORKS
【论文推荐】几何图形卷积网络，GEOM-GCN: GEOMETRIC GRAPH CONVOLUTIONAL NETWORKS
专知会员服务
75+阅读 · 2020年2月5日
Deep Learning Based Detection and Correction of Cardiac MR Motion Artefacts During Reconstruction for High-Quality Segmentation
Deep Learning Based Detection and Correction of Cardiac MR Motion Artefacts During Reconstruction for High-Quality Segmentation
专知会员服务
56+阅读 · 2019年10月17日
直播 | Interpretable and Trustworthy Graph Geometric Deep Learning
直播 | Interpretable and Trustworthy Graph Geometric Deep Learning
图与推荐
1+阅读 · 2022年11月2日
GNN 新基准！Long Range Graph Benchmark
GNN 新基准！Long Range Graph Benchmark
图与推荐
0+阅读 · 2022年10月18日
征稿 | International Joint Conference on Knowledge Graphs (IJCKG)
征稿 | International Joint Conference on Knowledge Graphs (IJCKG)
开放知识图谱
2+阅读 · 2022年5月20日
IEEE ICKG 2022: Call for Papers
IEEE ICKG 2022: Call for Papers
机器学习与推荐算法
3+阅读 · 2022年3月30日
ACM MM 2022 Call for Papers
ACM MM 2022 Call for Papers
CCF多媒体专委会
5+阅读 · 2022年3月29日
AIART 2022 Call for Papers
AIART 2022 Call for Papers
CCF多媒体专委会
1+阅读 · 2022年2月13日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium9
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium9
中国图象图形学学会CSIG
0+阅读 · 2021年12月17日
【ICIG2021】Latest News & Announcements of the Plenary Talk1
【ICIG2021】Latest News & Announcements of the Plenary Talk1
中国图象图形学学会CSIG
0+阅读 · 2021年11月1日
Hierarchically Structured Meta-learning
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
A Technical Overview of AI & ML in 2018 & Trends for 2019
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Marcks调节斑马鱼原肠胚形成中Bmp分泌和转运的机制研究
国家自然科学基金
0+阅读 · 2015年12月31日
一类稳态Schödinger-Poisson-Slater方程标准化解的研究
国家自然科学基金
1+阅读 · 2015年12月31日
分子显像监测TIGAR调节微环境诱导肿瘤转移及分子机制
国家自然科学基金
0+阅读 · 2014年12月31日
卵巢癌干细胞自分泌CCL5在肿瘤新生血管形成中的作用及机制研究
国家自然科学基金
0+阅读 · 2013年12月31日
Partial Spread Bent函数与Bent-Negabent函数的构造及密码学性质研究
国家自然科学基金
0+阅读 · 2013年12月31日
Dickkopf1调控血管形成的分子机制研究
国家自然科学基金
0+阅读 · 2012年12月31日
HIV-1 Nef蛋白促进KSHV K1诱导血管和肿瘤形成：信号通路与miRNAs的作用
国家自然科学基金
0+阅读 · 2012年12月31日
高效率集成化CMOS能量获取关键技术研究
国家自然科学基金
0+阅读 · 2012年12月31日
新型钠钙交换蛋白NCEX对糖尿病大血管病变的作用和黄芪多糖的干预机制
国家自然科学基金
0+阅读 · 2011年12月31日
海鞘多肽PCIA诱导细胞凋亡的分子机制
国家自然科学基金
0+阅读 · 2008年12月31日
Treewidth is NP-Complete on Cubic Graphs (and related results)
Arxiv
0+阅读 · 2023年1月24日
On the size of maximum cut in planar graphs
Arxiv
0+阅读 · 2023年1月22日
On the Algebraic Properties of Flame Graphs
Arxiv
0+阅读 · 2023年1月21日
Efficient Flow-based Approximation Algorithms for Submodular Hypergraph Partitioning via a Generalized Cut-Matching Game
Arxiv
0+阅读 · 2023年1月21日
ScaDLES: Scalable Deep Learning over Streaming data at the Edge
Arxiv
0+阅读 · 2023年1月21日
Trustworthy Graph Neural Networks: Aspects, Methods and Trends
Arxiv
11+阅读 · 2022年5月16日
Subgraph Neural Networks
Arxiv
27+阅读 · 2020年6月19日
Attributed Graph Clustering via Adaptive Graph Convolution
Arxiv
11+阅读 · 2019年6月4日
Semi-supervised Node Classification via Hierarchical Graph Convolutional Networks
Arxiv
14+阅读 · 2019年3月5日
Convolutional 2D Knowledge Graph Embeddings
Arxiv
29+阅读 · 2018年4月6日
VIP会员
文章信息
前往arXiv
下载PDF
相关主题
图
边
结点
离散数学
算法与数据结构
相关VIP内容
高效可扩展图神经网络的研究进展，Recent Advances in Efficient and Scalable Graph Neural Networks
高效可扩展图神经网络的研究进展，Recent Advances in Efficient and Scalable Graph Neural Networks
专知会员服务
75+阅读 · 2022年3月15日
71页PDF，Intro to the Metaverse（元宇宙概念发展透析），Newzoo Trend Report 2021
71页PDF，Intro to the Metaverse（元宇宙概念发展透析），Newzoo Trend Report 2021
专知会员服务
21+阅读 · 2022年2月19日
ICLR 2021杰出论文奖出炉，8篇论文上榜！
专知会员服务
25+阅读 · 2021年4月2日
一份简单《图神经网络》教程，28页ppt
一份简单《图神经网络》教程，28页ppt
专知会员服务
123+阅读 · 2020年8月2日
【新书】人工智能Python代码，227页pdf，Python code for Artificial Intelligence: Foundations of Computational Agents
【新书】人工智能Python代码，227页pdf，Python code for Artificial Intelligence: Foundations of Computational Agents
专知会员服务
99+阅读 · 2020年6月21日
50+篇《神经架构搜索NAS》2020论文合集
专知会员服务
60+阅读 · 2020年3月19日
100+篇《自监督学习(Self-Supervised Learning)》论文最新合集
100+篇《自监督学习(Self-Supervised Learning)》论文最新合集
专知会员服务
164+阅读 · 2020年3月18日
【新书】数字图像(影像)处理手第二版，2176pdf，Mathematical Methods in Imaging
【新书】数字图像(影像)处理手第二版，2176pdf，Mathematical Methods in Imaging
专知会员服务
88+阅读 · 2020年2月12日
【论文推荐】几何图形卷积网络，GEOM-GCN: GEOMETRIC GRAPH CONVOLUTIONAL NETWORKS
【论文推荐】几何图形卷积网络，GEOM-GCN: GEOMETRIC GRAPH CONVOLUTIONAL NETWORKS
专知会员服务
75+阅读 · 2020年2月5日
Deep Learning Based Detection and Correction of Cardiac MR Motion Artefacts During Reconstruction for High-Quality Segmentation
Deep Learning Based Detection and Correction of Cardiac MR Motion Artefacts During Reconstruction for High-Quality Segmentation
专知会员服务
56+阅读 · 2019年10月17日
热门VIP内容
相关资讯
直播 | Interpretable and Trustworthy Graph Geometric Deep Learning
直播 | Interpretable and Trustworthy Graph Geometric Deep Learning
图与推荐
1+阅读 · 2022年11月2日
GNN 新基准！Long Range Graph Benchmark
GNN 新基准！Long Range Graph Benchmark
图与推荐
0+阅读 · 2022年10月18日
征稿 | International Joint Conference on Knowledge Graphs (IJCKG)
征稿 | International Joint Conference on Knowledge Graphs (IJCKG)
开放知识图谱
2+阅读 · 2022年5月20日
IEEE ICKG 2022: Call for Papers
IEEE ICKG 2022: Call for Papers
机器学习与推荐算法
3+阅读 · 2022年3月30日
ACM MM 2022 Call for Papers
ACM MM 2022 Call for Papers
CCF多媒体专委会
5+阅读 · 2022年3月29日
AIART 2022 Call for Papers
AIART 2022 Call for Papers
CCF多媒体专委会
1+阅读 · 2022年2月13日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium9
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium9
中国图象图形学学会CSIG
0+阅读 · 2021年12月17日
【ICIG2021】Latest News & Announcements of the Plenary Talk1
【ICIG2021】Latest News & Announcements of the Plenary Talk1
中国图象图形学学会CSIG
0+阅读 · 2021年11月1日
Hierarchically Structured Meta-learning
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
A Technical Overview of AI & ML in 2018 & Trends for 2019
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
相关论文
Treewidth is NP-Complete on Cubic Graphs (and related results)
Arxiv
0+阅读 · 2023年1月24日
On the size of maximum cut in planar graphs
Arxiv
0+阅读 · 2023年1月22日
On the Algebraic Properties of Flame Graphs
Arxiv
0+阅读 · 2023年1月21日
Efficient Flow-based Approximation Algorithms for Submodular Hypergraph Partitioning via a Generalized Cut-Matching Game
Arxiv
0+阅读 · 2023年1月21日
ScaDLES: Scalable Deep Learning over Streaming data at the Edge
Arxiv
0+阅读 · 2023年1月21日
Trustworthy Graph Neural Networks: Aspects, Methods and Trends
Arxiv
11+阅读 · 2022年5月16日
Subgraph Neural Networks
Arxiv
27+阅读 · 2020年6月19日
Attributed Graph Clustering via Adaptive Graph Convolution
Arxiv
11+阅读 · 2019年6月4日
Semi-supervised Node Classification via Hierarchical Graph Convolutional Networks
Arxiv
14+阅读 · 2019年3月5日
Convolutional 2D Knowledge Graph Embeddings
Arxiv
29+阅读 · 2018年4月6日
相关基金
Marcks调节斑马鱼原肠胚形成中Bmp分泌和转运的机制研究
国家自然科学基金
0+阅读 · 2015年12月31日
一类稳态Schödinger-Poisson-Slater方程标准化解的研究
国家自然科学基金
1+阅读 · 2015年12月31日
分子显像监测TIGAR调节微环境诱导肿瘤转移及分子机制
国家自然科学基金
0+阅读 · 2014年12月31日
卵巢癌干细胞自分泌CCL5在肿瘤新生血管形成中的作用及机制研究
国家自然科学基金
0+阅读 · 2013年12月31日
Partial Spread Bent函数与Bent-Negabent函数的构造及密码学性质研究
国家自然科学基金
0+阅读 · 2013年12月31日
Dickkopf1调控血管形成的分子机制研究
国家自然科学基金
0+阅读 · 2012年12月31日
HIV-1 Nef蛋白促进KSHV K1诱导血管和肿瘤形成：信号通路与miRNAs的作用
国家自然科学基金
0+阅读 · 2012年12月31日
高效率集成化CMOS能量获取关键技术研究
国家自然科学基金
0+阅读 · 2012年12月31日
新型钠钙交换蛋白NCEX对糖尿病大血管病变的作用和黄芪多糖的干预机制
国家自然科学基金
0+阅读 · 2011年12月31日
海鞘多肽PCIA诱导细胞凋亡的分子机制
国家自然科学基金
0+阅读 · 2008年12月31日
Top
微信扫码咨询专知VIP会员
Top