2
$\begingroup$

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?

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

1 Answers 1

3

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.

  • 0
    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?2011-11-10
  • 0
    @CCSab, yes. 2011-11-10
  • 0
    @Peter: I think "maximal matching" should be replaced by "maximum matching" in the answer?2011-11-10
  • 0
    @joriki, thanks. Seems I've been using non-standard terms for years.2011-11-10
  • 0
    @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.2011-11-10
  • 0
    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.2011-11-10
  • 0
    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?2011-11-10
  • 0
    @Austin, yes, I checked the standard meanings between reading joriki's comment and updating the answer.2011-11-10
  • 0
    @CCSab, if you think about it a bit you should be able to adjust the weights so that two matchings with the same number of edges have weight ordering corresponding to their weight ordering under the original weights, but any matching with fewer edges has less weight.2011-11-10
  • 0
    @CCSab If you find multiple matchings that minimize the number of meals, you just need to compare their weights. You don't need an additional algorithm for this.2011-11-10