We study the complexity of the problems of finding, given a graph $G$, a largest induced subgraph of $G$ with all degrees odd (called an odd subgraph), and the smallest number of odd subgraphs that partition $V(G)$. We call these parameters ${\sf mos}(G)$ and $\chi_{{\sf odd}}(G)$, respectively. We prove that deciding whether $\chi_{{\sf odd}}(G) \leq q$ is polynomial-time solvable if $q \leq 2$, and NP-complete otherwise. We provide algorithms in time $2^{O({\sf rw})} \cdot n^{O(1)}$ and $2^{O(q \cdot {\sf rw})} \cdot n^{O(1)}$ to compute ${\sf mos}(G)$ and to decide whether $\chi_{{\sf odd}}(G) \leq q$ on $n$-vertex graphs of rank-width at most ${\sf rw}$, respectively, and we prove that the dependency on rank-width is asymptotically optimal under the ETH. Finally, we give some tight bounds for these parameters on restricted graph classes or in relation to other parameters.


翻译:我们研究了查找问题的复杂性, 给出了一个 G$ 的图形, 最大诱导的 G$ 和所有度的奇数( 称为奇数子图), 以及最小数量的 用于分割 $V( G) 的奇数子。 我们分别将这些参数称为 $@ sf mos}( G) 和 $\ chi ⁇ sf od{ ( G) 和 $\ chi ⁇ sf wid} ( G) q)\\ leq q q q q $( 奇数) 。 我们证明, 决定 美元=2 leq 2 美元和 NP- 完成的多元值 。 我们在时间上提供 $O (sf)\ (s)\ 美元 (sf) 美元 (sf) lax leq q $( q) q) 和 NPP- wex 美元 (w}}\\\\ 美元 (cd) lax lax lex- lex level- legy level legy lections legrof, legy lesh lex lex lesh

0
下载
关闭预览

相关内容

专知会员服务
44+阅读 · 2021年6月1日
专知会员服务
25+阅读 · 2021年4月2日
专知会员服务
50+阅读 · 2020年12月14日
神经常微分方程教程,50页ppt,A brief tutorial on Neural ODEs
专知会员服务
71+阅读 · 2020年8月2日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
MIT新书《强化学习与最优控制》
专知会员服务
275+阅读 · 2019年10月9日
分布式并行架构Ray介绍
CreateAMind
9+阅读 · 2019年8月9日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
ICLR2019最佳论文出炉
专知
12+阅读 · 2019年5月6日
Ray RLlib: Scalable 降龙十八掌
CreateAMind
9+阅读 · 2018年12月28日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Arxiv
0+阅读 · 2021年6月17日
Arxiv
0+阅读 · 2021年6月17日
Arxiv
0+阅读 · 2021年6月16日
An unifying point of view on expressive power of GNNs
Arxiv
0+阅读 · 2021年6月16日
VIP会员
相关VIP内容
专知会员服务
44+阅读 · 2021年6月1日
专知会员服务
25+阅读 · 2021年4月2日
专知会员服务
50+阅读 · 2020年12月14日
神经常微分方程教程,50页ppt,A brief tutorial on Neural ODEs
专知会员服务
71+阅读 · 2020年8月2日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
MIT新书《强化学习与最优控制》
专知会员服务
275+阅读 · 2019年10月9日
相关资讯
分布式并行架构Ray介绍
CreateAMind
9+阅读 · 2019年8月9日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
ICLR2019最佳论文出炉
专知
12+阅读 · 2019年5月6日
Ray RLlib: Scalable 降龙十八掌
CreateAMind
9+阅读 · 2018年12月28日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Top
微信扫码咨询专知VIP会员