[Solved]: Showing that minimal vertex deletion to a bipartite graph is NP-complete

Problem Detail: 

Consider the following problem whose input instance is a simple graph $G$ and a natural integer $k$.

Is there a set $S \subseteq V(G)$ such that $G - S$ is bipartite and $|S| \leq k$?

I would like to show that this problem is $\rm{NP}$-complete by reducing either 3-SAT, $k$-CLIQUE, $k$-DOMINATING SET or $k$-VERTEX COVER to it.

I believe I can reduce the 3-COLORING problem to it so I would only need to see how to reduce one of the mentioned problems to it. But since that would be rather messy I am wondering if someone sees an elegant reduction to the aforementioned problems.

Also, is there a name for this decision problem?

Asked By : Jernej

Answered By : Vor

Your problem is a special case of a broader class of problems named node-deletion problems:

J. M. Lewis and M. Yannakakis, "The node-deletion problem for hereditary properties is NP-complete"

... This paper deals with the class of graph problems defined as follows:
for a fixed graph property $\Pi$, find the minimum number of nodes (or vertices) which must be deleted from a given graph $G$ so that the result satisfies $\Pi$. We call this the node-deletion problem for $\Pi$. Our results show that if $\Pi$ is a nontrivial property which is hereditary on induced subgraph, then the node-deletion problem for $\Pi$ is NP-hard. Furthermore, if we add the condition that testing for $\Pi$ can be performed in polynomial time, then our results imply that the node-deletion problem for $\Pi$ is NP-complete. ...

Your problem is the node deletion problem for bipartiteness, but (as noted by Pal), it is known today as the Odd cycle traversal (OCT) problem.

EDIT

For what regards a direct reduction, I thought of this one from 3SAT.

Given an instance of 3SAT with $n$ variables and $m$ clauses, build the following graph: add two nodes $x_i, \overline{x_i}$ for each variable and an edge between them. To simulate a truth assignment, add $n+1$ nodes for each variable $x_i$ and connect them both to $x_i$ and $\overline{x_i}$; in this way, in order to make a bipartite graph deleting at most $n$ nodes, at least one between $x_i$ and $\overline{x_i}$ must be deleted . Finally for each clause $C_j$ add 4 nodes and build an odd cycle that connects the variables in $C_j$.

The resulting graph $G$ can be made bipartite deleting at most $n$ nodes if and only if the original 3SAT formula is satisfiable.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/9863