Homework 7

Demonstrate a reduction that shows that Minimum Node-Deletion Bipartite Subgraph (MNDBS) is at least as hard as Clique, where these problems are defined as:

Clique: Given k and a graph G with n nodes, is there a clique of size k?

MNDBS: Given k' and a graph G' with n' nodes, is there a set of only k' nodes that could be deleted to make this a bipartite graph? (A bipartite graph is one that can be partitioned into two sets of nodes with no edges between nodes in the same set.)

Hint:

Try letting k'=n-k, and n'=2*n. Try letting G' be the complement of G (all missing edges are added in and all existing edges are deleted) fully interconnected with an additional n nodes.