Homework 12 Solution

CS409 - Spring 2000

Due: Thursday, May 4

1. (15 points) Dating Problem [from Ahuja, Magnati, Orlin 1993].  A dating service receives data from p men and p women.  These data determine what pairs of men and women are mutually compatible.  Since the dating service's commission is proportional to the number of dates it arranges, it would like to determine the maximum number of compatible couples that can be formed.  Explain how to formulate this problem as a matching problem.  (Note that each man or women is assigned at most one date.)
   Create a vertex for each man and a vertex for each woman.  Draw an edge between each pair of vertices that correspond to a potential compatible couple.  Finding the maximum number of compatible couples corresponds to finding the maximum matching in this bipartite graph.

    

2. (15 points) Seat Sharing Problem [from Ahuja, Magnati, Orlin 1993].  Several families are planning a shared car trip on scenic drives in New Hampshire's White Mountains.  To minimize the possibility of any quarrels, they want to assign individuals to cars so that no two members of a family are in the same car.  Explain how to formulate this problem as a network flow problem. (Hint: the people are the "flow"; make sure you have the right number of people per family and the right number of people per car.)
   Create a source s, a sink t, a vertex for each family and a vertex for each car.   Each unit of flow corresponds to a person.  Connect the source to each of the family vertices with an edge of capacity equal to the family size; this places the right number of members in each family.  Connect each car-vertex to the sink with an edge of capacity equal to the car's number of passengers; this ensures that each car can carry the right number of people.  Connect each family vertex to every car vertex with an edge of capacity 1; this ensures that no more than one member of each family goes into any one car.  It's easy to see the correspondence between a satisfying assignment of people to cars and the max-flow in the graph.

    

3. (10 points) Consider the following flow network.
   1. What is the value of the maximum flow from s to t?
      The maximum possible flow is 12.
   2. Describe which edges are part of the minimum cut.
      The minimum cut corresponds to cutting all the edges that enter t.