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