For an undirected graph $G=(V,E)$ and a bound on the vertex degree $b: V \rightarrow \mathbb{N}$, I am looking into the problem of finding a maximal subset $H$ of $E$, such that each vertex $v\in V$ in the induced subgraph $G[H]$ has degree $\deg_{G[H]}(v)\leq b(v)$. The special case $b \equiv 1$ are matchings.
An interesting question is, how good does the greedy perform (pick edges until you can't add any further ones).
This book claims (Theorem 3.1), that the greedy gives an approximation ratio of $\dfrac{1}{2}$. To see this they take an arbitrary maximal $b$-Matching $M$ and a maximum $b$-Matching $M^*$ and consider $S=\{v \in V| \text{there are exactly }b(v) \text{ edges of M incident to }v\}$. Then they claim that every edge in $M^*$ must have an endpoint in $S$ as otherwise $M$ would not be maximal.
I have doubts in this claim: For the special case $M=M^*$ it means that a maximum $b$-Matching has not $2$ unsaturated nodes connected via a matching edge, but isn't this a counterexample:
(red = $M=M^*$, orange=$S$, node labels=$b(v)$)
Thank you for your help.
Best Answer
I agree with you - good counterexample! The proof can be fixed though. For example, note that $\frac{|M\setminus M^*|}{|M^*\setminus M|}\leq\frac{|M|}{|M^*|}$, so (after adjusting $b$ appropriately) it suffices to consider the case $M\cap M^*=\emptyset$.