Suppose you and your friend Alanis live together with n ? 2 other people at a popular cooperative apartment. Over the next n nights, each of you is supposed to cook dinner for the co-op exactly once, so some one cooks on each of the nights. To make things interesting, everyone has scheduling conflicts with some of the (e.g., exams, deadlines at work, basketball games, etc.), so deciding who should cook on which night becomes a tricky task. For concreteness, lets label the people {p1, . . . , pn} and the nights {d1, . . . , dn}. Then for person pi , associate a set of nights Si ? {d1, . . . , dn} when they are not available to cook. A feasible dinner schedule is defined to be an assignment of each person in the co-op to a different night such that each person cooks on exactly one night, there is someone to cook on each night, and if pi cooks on night dj , then dj ?/ Si .
(a) Describe a bipartite graph G such 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 work for the day. Unfortunately, when you look at the schedule she created, you notice a big problemn ? 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 she has accidentally assigned both pi and pj to cook on night dk and no one to cook on night dl . You want to fix the schedule but without having to recompute everything from scratch. Show that it is possible, using her almost correct schedule, to decide in only O(n 2 ) time whether there exists a feasible dinner schedule for the co-op. If one exists, your algorithm should also provide that schedule.
Suppose you and your friend Alanis live together with n 2 other people at a popular "cooperative" apartment. Over the next n nights, each of you is supposed to cook dinner for the co-op exactly once, so some one cooks on each of the nights. To make things interesting, everyone has scheduling conflicts with some of the (e.g., exams, deadlines at work, basketball games, etc.), so deciding who should cook on which night becomes a tricky task. For concreteness, let's label the people (pi, .> and the nights {di,....dn]. Then for person Pi, associate a set of nights Sd..dn when they are not available to cook. A feasible dinner schedule is defined to be an assignment of each person in the co-op to a different night such that each person cooks on exactly one night, there is someone to cook on each night, and if pi cooks on night dj, then d, S Describe a bipartite graph G such that G has a perfect matching if and only if there is a teasible dinner schedule for the co-op 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 work 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 p; and pj, and the other two days dk di, you discover she has accidentally assigned both p, and pj to cook on night dk and no one to cook on night di. You want to fix the schedule but without having to recompute everything from scratch. Show that it is 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, your algorithm and should also provide that schedule. Suppose you and your friend Alanis live together with n 2 other people at a popular "cooperative" apartment. Over the next n nights, each of you is supposed to cook dinner for the co-op exactly once, so some one cooks on each of the nights. To make things interesting, everyone has scheduling conflicts with some of the (e.g., exams, deadlines at work, basketball games, etc.), so deciding who should cook on which night becomes a tricky task. For concreteness, let's label the people (pi, .> and the nights {di,....dn]. Then for person Pi, associate a set of nights Sd..dn when they are not available to cook. A feasible dinner schedule is defined to be an assignment of each person in the co-op to a different night such that each person cooks on exactly one night, there is someone to cook on each night, and if pi cooks on night dj, then d, S Describe a bipartite graph G such that G has a perfect matching if and only if there is a teasible dinner schedule for the co-op 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 work 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 p; and pj, and the other two days dk di, you discover she has accidentally assigned both p, and pj to cook on night dk and no one to cook on night di. You want to fix the schedule but without having to recompute everything from scratch. Show that it is 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, your algorithm and should also provide that schedule
