Completely disconnecting a bipartite graph

Question

I have a disconnected bipartite undirected graph. I want to completely disconnect the graph. Only operation that I can perform is to remove a node. Removing a node will automatically delete its edges. Task is to minimize the number of nodes to be removed. Each node in the graph has atmost 4 edges.

By completely disconnecting a graph, I mean that no two nodes should be connected through a link. Basically an empty edge set.

Answer 1

I think, you cannot prove your algorithm is optimal because, in fact, it is not optimal.

To completely disconnect your graph minimizing the number of nodes to be removed, you have to remove all the nodes belonging to the minimal vertex cover of your graph. Searching the minimal vertex cover is usually NP-complete, but for bipartite graphs there is a polynomial-time solution.

Find maximum matching in the graph (probably with Hopcroft–Karp algorithm). Then use König's theorem to get the minimal vertex cover:

Consider a bipartite graph where the vertices are partitioned into left (L) and right (R) sets. Suppose there is a maximum matching which partitions the edges into those used in the matching (E_m) and those not (E_0). Let T consist of all unmatched vertices from L, as well as all vertices reachable from those by going left-to-right along edges from E_0 and right-to-left along edges from E_m. This essentially means that for each unmatched vertex in L, we add into T all vertices that occur in a path alternating between edges from E_0 and E_m.

Then (L \ T) OR (R AND T) is a minimum vertex cover.

Answer 2

Here's a counter-example to your suggested algorithm.

The best solution is to remove both nodes A and B, even though they are different colors.