Graph modification problems are computational tasks where the goal is to change an input graph $G$ using operations from a fixed set, in order to make the resulting graph satisfy a target property, which usually entails membership to a desired graph class $\mathcal{C}$. Some well-known examples of operations include vertex-deletion, edge-deletion, edge-addition and edge-contraction. In this paper we address an operation known as subgraph complement. Given a graph $G$ and a subset $S$ of its vertices, the subgraph complement $G \oplus S$ is the graph resulting of complementing the edge set of the subgraph induced by $S$ in $G$. We say that a graph $H$ is a subgraph complement of $G$ if there is an $S$ such that $H$ is isomorphic to $G \oplus S$. For a graph class $\mathcal{C}$, subgraph complementation to $\mathcal{C}$ is the problem of deciding, for a given graph $G$, whether $G$ has a subgraph complement in $\mathcal{C}$. This problem has been studied and its complexity has been settled for many classes $\mathcal{C}$ such as $\mathcal{H}$-free graphs, for various families $\mathcal{H}$, and for classes of bounded degeneracy. In this work, we focus on classes graphs of minimum/maximum degree upper/lower bounded by some value $k$. In particular, we answer an open question of Antony et al. [Information Processing Letters 188, 106530 (2025)], by showing that subgraph complementation to $\mathcal{C}$ is NP-complete when $\mathcal{C}$ is the class of graphs of minimum degree at least $k$, if $k$ is part of the input. We also show that subgraph complementation to $k$-regular parameterized by $k$ is fixed-parameter tractable.


翻译:暂无翻译

0
下载
关闭预览

相关内容

【ACL2020】多模态信息抽取,365页ppt
专知会员服务
150+阅读 · 2020年7月6日
FlowQA: Grasping Flow in History for Conversational Machine Comprehension
专知会员服务
33+阅读 · 2019年10月18日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
159+阅读 · 2019年10月12日
强化学习最新教程,17页pdf
专知会员服务
181+阅读 · 2019年10月11日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
41+阅读 · 2019年10月9日
RL解决'BipedalWalkerHardcore-v2' (SOTA)
CreateAMind
31+阅读 · 2019年7月17日
强化学习的Unsupervised Meta-Learning
CreateAMind
18+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
STRCF for Visual Object Tracking
统计学习与视觉计算组
14+阅读 · 2018年5月29日
Focal Loss for Dense Object Detection
统计学习与视觉计算组
11+阅读 · 2018年3月15日
IJCAI | Cascade Dynamics Modeling with Attention-based RNN
KingsGarden
13+阅读 · 2017年7月16日
国家自然科学基金
1+阅读 · 2017年12月31日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
2+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
5+阅读 · 2014年12月31日
Arxiv
0+阅读 · 3月19日
VIP会员
相关资讯
RL解决'BipedalWalkerHardcore-v2' (SOTA)
CreateAMind
31+阅读 · 2019年7月17日
强化学习的Unsupervised Meta-Learning
CreateAMind
18+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
STRCF for Visual Object Tracking
统计学习与视觉计算组
14+阅读 · 2018年5月29日
Focal Loss for Dense Object Detection
统计学习与视觉计算组
11+阅读 · 2018年3月15日
IJCAI | Cascade Dynamics Modeling with Attention-based RNN
KingsGarden
13+阅读 · 2017年7月16日
相关基金
国家自然科学基金
1+阅读 · 2017年12月31日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
2+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
5+阅读 · 2014年12月31日
Top
微信扫码咨询专知VIP会员