Maximum Independent Set Algorithm

Question

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.

Answer 1

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.

Answer 2

As Aaron McDaid mentions in his now deleted answer, the problem of find a maximum independent set is equivalent to finding a maximum clique. The equivalence is that finding a maximum independent set in a graph G is the same as finding a maximum clique in the complement of G. The problem is known to be NP-complete.

The brute force solution you mention takes O(n^2 2^n), but you can do better than this. Robson has a paper entitled ""Algorithms for maximum independent sets" from 1986 that gives an algorithm that takes O(2^{c*n}) for a constant 0<c<1 (I believe c is around 1/4, but I could be mistaken). None of this is specific to a bipartite graph.

One thing to note if you have a bipartite graph is that either side forms an independent set. In the complete bipartite graph K_{b,r} which is partitioned B x R with |B|=b and |R|=r where there is an edge from every vertex in B to every vertex in R and none within B nor none within R, a maximum independent set is B if b>=r, otherwise it's R.

Taking B or R won't work in general. sdcvvc noted the example with vertices {1,2,3,A,B,C} and edges {A,1}, {A,2}, {A,3}, {B,3}, {C,3}. In this case, the maximal independent set is {1,2,B,C}, which is larger than either partition {A,B,C} or {1,2,3}.

It may improve Robson's algorithm to start with the larger of B or R and proceed from there, though I'm not sure how much of a difference this will make.

Alternatively, you can use the Hopcroft–Karp algorithm on the bipartite complement of a graph to find a maximum matching, and then take the vertices used in the matching as the independent set. This gives a polynomial time algorithm to solve the problem.