0
$\begingroup$

Let's say I have a graph that is not bipartite. Let's say it is colored red and black and there are some conflicts where two vertices of the same color share an edge. I can introduce a new vertex between them of the opposite color, breaking the edge into two. Now I have removed that conflict. I can continue doing this until the modified graph is bipartite.

Question:

How do you do this in a way to minimize the number of vertices added? I don't want to assume that the graph is already colored. That was just to help explain the process.

$\endgroup$
7
$\begingroup$

You want to partition the vertices into two parts and minimizing the number of edges between vertices in the same part. In other words you want to maximize the number of edges between the two parts. This is know as the max-cut problem and is NP-hard and APX-hard.

$\endgroup$

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.