HackerPapers

arXiv:1403.5544cs.CC

Yet Another Graph Partitioning Problem is NP-Hard

Ryan H. Lewis

HN submission. Found in a submission link or body. Submitters do not count as commenters in the main ranking; a submission is not an endorsement.

Abstract

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.

arXiv comments
Journal reference
DOI
Subjects
cs.CCComputational Complexity cs.DSData Structures and Algorithms

On Hacker News

No comments linking this paper were found in the collected sources. Found in 1 HN submission from Mar 2014 to Mar 2014. Open submission discussions.

Comments linking this paper, per year.

Discussed in comments0 threads

No comments linking this paper were found in the collected sources. Open submission discussions.

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.