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?

  • 6
    $\begingroup$ Odd Cycle Transversal. $\endgroup$ – Pål GD Feb 17 '13 at 19:21
  • $\begingroup$ This seems similar to feedback vertex set. That is, you want to find minimum subset of vertices to remove such that the resulting graph is acyclic. An acyclic graph is by definition a tree (or forest) which is bipartite. $\endgroup$ – Nicholas Mancuso Feb 17 '13 at 21:37
  • $\begingroup$ @NicholasMancuso It is not so similar. It is really as I say above, the Odd Cycle Transversal problem. Or as Vor points out, was called the Bipartite node (or vertex) deletion by Yannakakis in the 70s and 80s. $\endgroup$ – Pål GD Feb 17 '13 at 21:42
  • $\begingroup$ @PålGD, I agree. I felt that the easiest reduction would be from FVS. However, that is made unnecessary by its definition as Odd Cycle Transversal. $\endgroup$ – Nicholas Mancuso Feb 17 '13 at 23:00
  • 2
    $\begingroup$ @Jernej: you say "... I would like to show that this problem is in NP by reducing it either to 3-SAT, the k-CLIQUE, ...". Do you mean "I would like to show that this problem is NP-hard using a reduction from 3-SAT, k-CLIQUE, ..." ? (the problem is clearly in NP because testing if a graph is bipartite can be done in linear time) $\endgroup$ – Vor Feb 17 '13 at 23:10

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.


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.

enter image description here

  • $\begingroup$ This isn't really the answer the question asks for. OP want to reduce explicitly using the given problem. Furthermore, the problem is known today as Odd Cycle Transversal. $\endgroup$ – Pål GD Feb 17 '13 at 19:28
  • $\begingroup$ @PålGD: you're right. $\endgroup$ – Vor Feb 17 '13 at 19:40
  • $\begingroup$ Yeah, but I can't immediately see a reduction from OP's list of problems, though ... I only know of the one you mention, by Yannakakis. $\endgroup$ – Pål GD Feb 17 '13 at 20:02
  • $\begingroup$ @PålGD: I'll think about a different reduction, but to be honest I'm not sure of what exactly the OP wants (see my comment above). $\endgroup$ – Vor Feb 17 '13 at 23:12
  • $\begingroup$ @Vor What I want is to see a simple reduction to one from one of the mentioned problems. This article is known to me but I am rather looking for the most direct reduction. $\endgroup$ – Jernej Feb 18 '13 at 9:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.