We wish to find the maximum independent set in a bipartite graph. My intuition led me to the following algorithm. (Assume that the bipartite graph is connected and has at least 3 vertices, if not run the algorithm on each component)

  1. Given $G=(L,R,E)$
  2. Let $S$ be the set of vertices with degree $1$. Note that since graph is connected and has at least $3$ vertices, $v,u\in S\implies (v,u)\not \in E$. (If $S$ is empty, go to step $5$)
  3. Add the vertices in $S$ to the independent set. $\forall s\in S$, remove $s$ and neighborhood of $s$ from $G$
  4. If the graph is connected, repeat steps $2-4$. If it is disconnected, repeat the steps $2-4$ for each component.
  5. if $|L| > |R|$, add $L$ to the independent set, else add $R$

Obviously, the output is some independent set, not necessarily the maximum. However, I could neither prove nor come up with an counter example. Any help will be appreciated.

https://cs.stackexchange.com/a/3033 has a answer which does not rely on intuition


1 Answer 1


Consider the following graph:

bipartite graph

None of the vertices has degree 1, so we go straight to step 5. Your algorithm would return 5 as the maximum independent set size, as both $L$ and $R$ have 5 vertices. However, the actual maximum independent set is $\{1, 2, 3, 6, 7, 8\}$, which has 6 vertices.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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