1
$\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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
10
$\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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .