New answers tagged

3

These are not directly comparable: Goemans–Williamson and related work: find a cut in any graph G [of some graph family] that is at least X times the size of the maximum cut of G. This is the usual approximation ratio. The paper mentioned in the question and related work: find a cut in any graph G [of some graph family] that contains at least X fraction of ...


0

To answer my own question, I have found that this problem is indeed NP-Hard via a reduction from the Cactus Augmentation Problem (which is NP-hard). In "Parameterized Algorithms to Preserve Connectivity" they show that a Cactus Augmentation Problem can be transformed into an equivalent Node-weighted Steiner Tree problem where each Steiner node is ...


Top 50 recent answers are included