Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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: enter image description here

(red = $M=M^*$, orange=$S$, node labels=$b(v)$)

Thank you for your help.

share|improve this question

1 Answer 1

up vote 2 down vote accepted

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$.

share|improve this answer
    
Thank you, I looked for something like this. –  Listing Jun 29 '12 at 18:01

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.