在平面图中具有多项式时间解的一般NP难问题列表是什么？

Question

7

我遇到了很多可以表述为图形问题的难题。一般情况下，这些问题是NP难的，但有时可以证明该图形是平面图。因此，我对学习这些问题和算法很感兴趣。

据我所知，目前为止包括以下几个问题：

1. 平面图中的最大割 2. 平面图的四色定理 3. 三次平面图中的最大独立集

希望有人能够补充这个列表。

- Ivan Xiao

我认为这个问题应该属于cstheory.se。 - Alexandru

看了他们的FAQ，我认为cstheory.se可能会关闭这个问题。 - Bill the Lizard

我之前关闭了这个问题，因为它看起来像一个"X列表"的问题，但是我重新打开希望有一个资源能够给出答案。如果其他人认为没有一个正确的答案，他们可以投票关闭。 - Bill the Lizard

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- borrible · Accepted Answer

在NP完全问题的概述中，索引中的平面图部分包含大约25个条目。这些条目通常链接到平面输入可以接受PTAS的问题。