Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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
up vote 3 down vote accepted

Flip your edges: make them edges between pairs of food which can be eaten together. Then a maximum matching gives you the two-food meals, and the unmatched nodes are the one-food meals.

share|cite|improve this answer
If I use something like Edmond's algorithm, which runs in polynomial time, will this still work? Basically, what I'm trying to say is what the integral difference between maximum and maximal matching means with respect to this problem. My train of thought is that if I find the maximum matching, this maximizes the number of 2-food meals, which means that I can eat all the food in the least amount of meals. Am I correct in this reasoning? – CCSab Nov 10 '11 at 9:22
@CCSab, yes. <!-- padding --> – Peter Taylor Nov 10 '11 at 9:25
@Peter: I think "maximal matching" should be replaced by "maximum matching" in the answer? – joriki Nov 10 '11 at 9:37
@joriki, thanks. Seems I've been using non-standard terms for years. – Peter Taylor Nov 10 '11 at 9:42
@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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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