2
$\begingroup$

I am quite familiar with Ford-Fulkerson algorithm but I am having a trouble to apply the algorithm to the following problem. Can someone please give me some hints or better instructions how to use FF method to this problem?

Let O be a set of n objects. It is required to form a set G of m groups. There are three possibly overlapping subsets of objects: A, B and C. Each object belongs to one or more of these subsets. Each object can be assigned to at most one group. It is required that every group must have at least ten objects: two are from subset A, three others are from subset B, and one other is from subset C; the remaining objects can be from any subset.

It is required to explain how to apply the Ford-Fulkerson algorithm to determine whether it is possible to assign n objects to m groups according to the given rules.

Small addendum (See below the idea suggested by @D.W.): In case of only two subsets A and B, the flow network could look like that (?). I assume that capacities c1, c2, c3 can be found from subset A and B

enter image description here

$\endgroup$
2
  • $\begingroup$ Can you provide a reference to the original source where you encountered this? Why do you think that it is possible to solve this in the way indicated? $\endgroup$ – D.W. Dec 2 '20 at 17:33
  • $\begingroup$ @D.W. I found the problem in the past exam paper (year 2013, UfT). Do you find it weird? I do! Cross-posted question was deleted! $\endgroup$ – Alex C Dec 2 '20 at 18:33
1
$\begingroup$

I suggest you start with a simpler problem: there are only two (possibly overlapping) subsets, A and B; and every group must have two objects: one from subset A, and one from B.

Once I figured out how to solve that, it was clear to me how to solve your original question.

Hint on how to solve that:

Have one left vertex per object. Have two right vertices per group, one to represent which object is chosen from subset A, and one to represent which object is chosen from subset B. Now figure out how to fill in the edges...

$\endgroup$
5
  • $\begingroup$ Hm... In this case, at least how many objects should be in one group? I still have no clue about overlapping also. $\endgroup$ – Alex C Dec 2 '20 at 23:29
  • $\begingroup$ @AlexC, start with requiring exactly 2 in every group. Overlapping is exactly the core challenge... figure out how to handle that, and you're set! $\endgroup$ – D.W. Dec 3 '20 at 0:17
  • $\begingroup$ I added the flow network for the case with only two subsets. Any comments? Thanks! $\endgroup$ – Alex C Dec 3 '20 at 2:54
  • $\begingroup$ @AlexC, no, I don't think that works. Try to work through an example and see what solution it gets you. I think one node per subset is not going to work; you'll probably need at least one node per object. $\endgroup$ – D.W. Dec 3 '20 at 3:24
  • $\begingroup$ @AlexC, I saw you requested another hint. See the edited answer. $\endgroup$ – D.W. Dec 13 '20 at 4:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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