title: Maximum Independent Set Algorithm
body: <p>I don't believe there exists an algorithm for finding the maximum independent vertex set in a bipartite graph other than the brute force method of finding the maximum among all possible independent sets.</p>
  
  <p>I am wondering about the pseudocode to find all possible vertex sets.</p>
  
  <p>Say given a bipartite graph with 4 blue vertices and 4 red. Currently I would </p>
  
  <pre><code>Start with an arbitrary blue,
    find all red that don't match this blue
    put all these red in Independent Set
    find all blue that dont match these red
    put these blue in Independent Set
    Repeat for next vertex in blue
  
  Repeat all over again for all blue then all vertices in red.
  </code></pre>
  
  <p>I understand that this way doesn't give me all possible Independent Set combinations at all, since after the first step I am choosing all of the next colour vertices that dont match rather than stepping through every possiblity.</p>
  
  <p>For example given a graph with the matching</p>
  
  <pre><code>B  R
  1  1
  1  3 
  2  1
  2  3
  3  1
  3  3
  4  2
  4  4
  
  Start with blue 1
    Choose red 2 and 4 since they dont match
    Add 2, 4 to independent Set
    Choose 2 and 3 from blue since they dont with 2 or 4 from red
    Add 2 and 3 from blue to independent set as well.
  Independent Set = 1,2,3 from blue 2,4 from red
  Repeat for blue 2, blue 3, ... red n (storing the cardinality for each set)
  </code></pre>
  
  <p>Is there a way I can improve this algorithm to better search for all possibilities. I know that a |Maximum Set for a bipartite graph| = |Red| + |Blue| - |Maximum Matching|.</p>
  
  <p>The problem arises with the possibility that by choosing all possible red in the first go for a given blue, if those red connect to all other possible blue then my set only ever has all 1 blue and rest red.</p>