Finding Augmented-Set Bases
Virgil D. Gligor, David Maier · SIAM Journal on Computing · 1982
The problem of finding a minimum-cost, augmented-set basis is NP-complete. In this paper we show that this problem is not approximable. That is, if ${\text{P}} e {\text{NP}}$, then no constants c and d exist so that $A \leqq c{\text{ASB}} + d$, where A is the cost provided by a polynomial-time approximation algorithm and ASB is the optimal cost. We also provide a brief characterization of the cost functions for which this result remains valid. The proof technique used in the augmented-set basis problem is applied directly to other NP-complete problems, such as several graph augmentation and deletion problems, to show that they are also not approximable.