Question

Suppose you and your friend Alanis live, together with n − 2 other people, at a popular off-campus cooperative apartment, the Upson Collective. Over the next n nights, each of you is supposed to cook dinner for the co-op exactly once, so that someone cooks on each of the nights. Of course, everyone has scheduling conflicts with some of the nights (e.g., exams, concerts, etc.), so deciding who should cook on which night becomes a tricky task. For concreteness, let’s label the people {p1, . . . , pn},the nights {d1, . . . , dn}; and for person pi, there’s a set of nights Si⊂ {d1, . . . , dn}when they are not able to cook. A feasible dinner schedule is an assignment of each person in the coop to a different night, so that each person cooks on exactly one night, there is someone cooking on each night, and if picooks on night dj, then dj∈ Si. (a) Describe a bipartite graph G so that G has a perfect matching if and only if there is a feasible dinner schedule for the co-op. (b) Your friend Alanis takes on the task of trying to construct a feasible dinner schedule. After great effort, she constructs what she claims is a feasible schedule and then heads off to class for the day. Unfortunately, when you look at the schedule she created, you notice a big problem. n − 2 of the people at the co-op are assigned to different nights on which they are available: no problem there. But for the other two people, pi and pj, and the other two days, dk and dl, you discover that she has accidentally assigned both pi and pj to cook on night dk, and assigned no one to cook on night dl. You want to fix Alanis’s mistake but without having to recompute everything from scratch. Show that it’s possible, using her “almost correct” schedule, to decide in only O(n2) time whether there exists a feasible dinner schedule for the co-op. (If one exists, you should also output it)

Answer 1

a)

It is given that there are n people and n nights. Thus, it
is required to assign each person pto a night such
that p available to cook on night d,

By observing, we can conclude that, assigning persons
to available nights to cook is a matching problem.
Particularly, since it is required to assign a person to
only one night, the assignment should be a perfect
matching

We can find this perfect matching as follows:
First, build a bipartite graph. Take two sets of vertices.
One is the set of people. (p.p2 Poland another is
the set of nights,(d.djd).
• Now add an edge (p, d) to bipartite graph if the
person p, is available to cook on night d

• To find whether there is a perfect matching or not, we
can use maximum flow algorithm
· Add two more vertices, source vertex(s and sink
vertex to bipartite graph. Add edges from sto each
person. Also, add edges from each night to t

• Set each edge's capacity to 1
• Now, run the maximum flow algorithm. The schedule
will be feasible, if and only if the maximum flow is n
and the graph has exactly n edges (perfect matching).
If there is a maximum flow with value n and graph has
exactly edges, each person will be joined to a
distinct night. Thus, the matching gives the feasible
dinner schedule.
If there is no such maximum flow, there will be no
feasible dinner schedule.

b)
It is given that p and p both are assigned to dh and no one is assigned to cook on night di
• If there exists a feasible schedule, then there is a possibility that either
di S, and die For)
di S. and Scor)
die Sandd ES (or)
dieS and dies

• If du Sand dies then it is enough to add edge ( Pd). Otherwise we need find an edge
Pr. dr) to assign py to either dord and need to assign either and pto de
Algorithm FIX SCHEDULE
DeSi and S, then
2) Update edges in the graph (p. d) and ( d) and exit the loop
Il print the schedule
3)
for each edge (pad)
4)
print (p is assigned to night)
5) return !
1 indicates that there exists a feasible dinner schedule
6) Flag-False
7) Flag False
8) If doES, theu
9) for each edge (p. d)
10)
If die Saud de Sithen

Update edges in the graph (p. d) and (peda)
12)
Flag=Tie
13)
exit the loop
14) che
15) Flagl-True
16) If d eS, then
17) for each edged )
18)
If di Sg and d e S, then
19)
Update edges in the graph (pd) and ipod
20)
Flag2-True
21)
exit the loop
22) else
23) Flag2-Tnue

/if both flags are true, then there exists a feasible dinner schedule
24) If Flac=True and Flag=True then

l print the schedule
25) for each other (
pd.)
26)
print (p is assigned to cook night di
27 return 1 indicates that there exists a feasible dinner schedule
28) else
29)
return O
I/O indicates that there exists no feasible dinner schedule

Running time analysis:
• Consider the code fragment from lines 8 to 15 and code fragment from lines 16 to 23
• Both fragments take same ninning time.
• Consider the for loop at line 9, which takes O(n), since in the feasible dinner schedule,
there will be only edges.
. Consider the code at line 10. In the worst case, checking membership of as set takes On).
• Thus, the overall running time of the code fragment is O ).
Therefore, we can check whether there exists feasible dinner schedule or not in O(n) time.