# Conflicting Node Matching Problem

I am trying to figure out the following graph problem, and the best way to solve it.

I have a set of n nodes, which represent foods. One or two foods can be eaten each meal, but some pairs of foods cannot be eaten together. Given the combinations of foods that can't be eaten together, I am trying to develop an algorithm that will allow me to eat all the foods in the smallest number of meals.

What I am trying to do is formulate the problem as a graph matching problem. Each node represents a food, and an edge between nodes means that the two foods cannot be eaten together. However, I am not sure how to use a matching algorithm to solve the problem. Furthermore, I am not sure if this is the best way to solve the problem.

Here's something that I am trying to expand on: I want to add weights to the edges. I still want the fewest number of meals, but I want to maximize the sum of the weights of the edges. Running just a maximum weight algorithm doesn't guarantee me the fewest meals.

In the case that I have multiple matchings that minimize the number of meals, I feel that I can then run a maximum weight matching algorithm on the result to find the solution that maximizes the sum of the weights. Is this a correct train of thought?

-
I see. Maybe I'm approaching the problem incorrectly then, because I am supposed to develop a polynomial time algorithm. –  CCSab Nov 10 '11 at 8:54
@Austin: Your comment applies if the condition that only one or two foods can be eaten in each meal is dropped. –  joriki Nov 10 '11 at 9:34
@CCSab I misread your problem. What joriki says is correct. Please disregard my comment about graph coloring. –  Austin Mohr Nov 10 '11 at 10:05

@PeterTaylor Both words are in still in use, but they have different meanings. A "maximum matching" is a matching of largest possible size for the graph at hand. A "maximal matching" is a particular matching to which no new edges can be added. For example, imagine $K_4 - e$ as a box with a diagonal through it. Two parallel sides of the box form a maximum matching (and is, in fact, a perfect matching). The diagonal edge forms a maximal matching, since no edge can be added to it without violating the condition of being a matching. –  Austin Mohr Nov 10 '11 at 10:10