0
$\begingroup$

(there is the possibility that the answer to my question is "Traveling Salesman, dude!". If that is the case, Please just say so and I'll try it again on my own using Traveling Salesman. We have not covered that in the lecture yet.)

again I am facing homework and thus, would appreciate it, if you did not(!) give me the solution, but helped me to get there on my own.

I've got an exercise to solve and I think, I'm pretty close, but I seem to can't get there.

I've got a graph and have to color the vertices such that the following conditions are met:

-there are two colors (a,b)

-each edge has precisely ONE a-colored vertex

-the number of a-colored vertices is minimal

I've tried to reduce the problem to 2-coloring. BUT: I don't know how to deal with the condition that the number of a-colored vertices has to be minimal. I am pretty sure that I can reduce it to a coloring problem, because I also need to show NP-completeness.

Can anyone push me into the right direction?

Improve this question
$\endgroup$
1
  • $\begingroup$ Your problem is not NP-complete. It's in P. $\endgroup$
    – Yuval Filmus
    Feb 1, 2016 at 16:29

1 Answer 1

Reset to default
3
$\begingroup$

A valid coloring exists iff the graph is bipartite. In that case, you can divide it into its connected components. Suppose that the $i$th connected component has $x_i$ vertices on one side, and $y_i$ on the other side. Which side would you color $a$?

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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