The Effect of a Connectivity Requirement on the Complexity of Maximum Subgraph Problems
The Effect of a Connectivity Requirement on the Complexity of Maximum Subgraph Problems
复制标题
连接性要求对最大子图问题复杂性的影响
DOI：
--
复制
发表时间：
1979
期刊：
影响因子：
--
通讯作者：
M. Yannakakis
中科院分区：
文献类型：
--
作者：
M. Yannakakis
如果Ir是图的一个性质（或有向图），相应的最大子图问题是给定一个图G，求G的一个最大（诱导）子图满足性质~r。（导出子图上可遗传的性质类）增加连通性要求对~的影响证明了对于同一性质类，连通极大子图问题也是NP-难的，而且对于某个重要性质子类，即使以任何“合理”的方式近似它的节点删除版本也是NP难的。一组相关的问题被证明是A~ # NP LI co-NP，在这种情况下，NP # co-NP。
If Ir IS a property on graphs (or digraphs), the corresponding maximum subgraph problem is Given a graph G find a maximum (induced) subgraph of G satisfying property ~r The author has previously shown this problem to be NP-hard for a large class of properties (the class of properties that are hereditary on induced subgraphs) The effect of adding a connectwtty requirement to ~r is now considered It is shown that for the same class of properties the connected maximum subgraph problem is also NP-hard, moreover, for a certain important subclass of properties, even approximating the node-deletion version of it in any "reasonable" way is NP-hard A related set of problems is shown to testify to A~ # NP LI co-NP, In the case that NP # co-NP.