algorithmmaxgraph-theorynpindependent-set

Maximum Independent Set Algorithm

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.

I am wondering about the pseudocode to find all possible vertex sets.

Say given a bipartite graph with 4 blue vertices and 4 red. Currently I would 

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.

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.

For example given a graph with the matching

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)

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

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.

Solution

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

    There is: finding the maximum independent set is equivalent to finding the minimum vertex cover (by taking complement of the result), and Konig's theorem states that minimum vertex cover in bipartite graphs is equivalent to maximum matching, and that that can be found in polynomial time. I don't know about finding all matchings, but it seems there can be exponentially many.