A graph class is hereditary if it is closed under vertex deletion. We give examples of NP-hard, PSPACE-complete and NEXPTIME-complete problems that become constant-time solvable for every hereditary graph class that is not equal to the class of all graphs.
翻译：图形类如果在顶端删除下关闭,则具有遗传性。 我们举例说明NP-hard、PSPACE- complete和NEXPTIME- complete问题,这些问题对于与所有图表类不相等的每个遗传类图来说,都是固定时间可以溶解的。
相关内容
Arxiv
0+阅读 · 2021年10月6日
Arxiv
0+阅读 · 2021年10月4日
相关VIP内容
相关资讯
相关论文
Arxiv
0+阅读 · 2021年10月6日
Arxiv
0+阅读 · 2021年10月4日
微信扫码咨询专知VIP会员