New answers tagged approximation-algorithms
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