A Simplified Analysis of the Good-Bad $3/2$-Approximation Algorithm for Some Minimum-Cost Graph Problems

Abstract

In this paper, we consider an easy greedy approximation algorithm, the good-bad algorithm, introduced by Couëtoux for finding a minimum-cost set of edges such that every connected component has at least $k$ vertices. Couëtoux proves that the good-bad algorithm achieves a $3/2$-approximation for this problem. Davis and Williamson extend this result to the more general problem of finding a minimum-cost edge set that contains at least one edge from every cut $S\subseteq V$ satisfying $h(S)=1$ where $h:2^V\to \{0,1\}$ is downward monotone; that is, $h(S)=1$ implies $h(T)=1$ for every nonempty subset $T\subseteq S$. The original problem corresponds to $h(S)=1$ when $|S|<k$. We give a simplified analysis of the good-bad algorithm for downward monotone functions.