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
    @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
    @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