Yet Another Graph Partitioning Problem is NP-Hard

الأصل · EN

Recently a large number of graph separator problems have been proven to be 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.