The generalized coloring numbers of Kierstead and Yang [7] offer an algorithmically useful characterization of graph classes with bounded expansion. In this work, we consider the hardness and approximability of these parameters. First, we show that it is NP-hard to compute the weak 2-coloring number (answering an open question of Grohe et al. [5]). We then complete the picture by proving that the $r$-coloring number is also NP-hard to compute for all $r \geq 2$. Finally, we give an approximation algorithm for the $r$-coloring number which improves both the runtime and approximation factor of the existing approach of Dvo\v{r}\'ak [3]. Our algorithm greedily orders vertices with small enough $i$-reach for every $i \leq r$ and achieves an $O(C_{r-1} k^{r-1})$-approximation, where $C_j$ is the $j$th Catalan number.


翻译:Kierstead 和 Yang 的通用彩色数字[7] 提供了具有约束性扩展的图表类别具有逻辑价值的描述。 在这项工作中,我们考虑了这些参数的难度和近似性。 首先,我们表明,很难计算微弱的2色数字(回答Grohe et al. [5] 的未决问题) 。然后,我们通过证明美元彩色数字也很难计算所有2美元。最后,我们给出了美元彩色数字的近似算法,这改善了Dvo\v{r ⁇ 'ak [3] 的现行方法的运行时间和近似系数。我们的算法贪婪命令,每1美元以小的美元达到1美元,达到1美元(czr-1} k ⁇ r-1}-approximation。 最后,我们给出了美元数字的近似算法, 美元是美元卡塔兰数字。

0
下载
关闭预览

相关内容

专知会员服务
69+阅读 · 2021年3月23日
专知会员服务
84+阅读 · 2020年12月5日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
《DeepGCNs: Making GCNs Go as Deep as CNNs》
专知会员服务
30+阅读 · 2019年10月17日
【新书】Python编程基础,669页pdf
专知会员服务
194+阅读 · 2019年10月10日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
神经网络学习率设置
机器学习研究会
4+阅读 · 2018年3月3日
已删除
将门创投
5+阅读 · 2017年11月22日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Arxiv
0+阅读 · 2022年2月22日
Eternal Domination and Clique Covering
Arxiv
0+阅读 · 2022年2月21日
Arxiv
0+阅读 · 2022年2月21日
Arxiv
0+阅读 · 2022年2月21日
Arxiv
0+阅读 · 2022年2月19日
Arxiv
0+阅读 · 2022年2月18日
VIP会员
相关资讯
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
神经网络学习率设置
机器学习研究会
4+阅读 · 2018年3月3日
已删除
将门创投
5+阅读 · 2017年11月22日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
相关论文
Arxiv
0+阅读 · 2022年2月22日
Eternal Domination and Clique Covering
Arxiv
0+阅读 · 2022年2月21日
Arxiv
0+阅读 · 2022年2月21日
Arxiv
0+阅读 · 2022年2月21日
Arxiv
0+阅读 · 2022年2月19日
Arxiv
0+阅读 · 2022年2月18日
Top
微信扫码咨询专知VIP会员