

























Recently a large number of graph separator problems have been proven to be \textsc{NP-Hard}. Amazingly we have found that $α$-Subgraph-Balanced-Vertex-Separator, an important variant, has been overlooked. In this work ``Yet Another Graph Partitioning Problem is NP-Hard" we present the surprising result that $α$-Subgraph-Balanced-Vertex-Separator is $NP$-Hard. This is despite the fact that the constraints of our new problem are harder to satisfy than the original problem.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。