2) A critical document has to be sent from Ougadougou to Timbuktu. To ensure that it reaches safely, three copies are made and entrusted to three different people to carry to the destination. They will each take a sequence of trains, buses, and flights. To ensure that the document reaches safely, the three couriers are not allowed to take the same train, bus, or flight at any stage along the route.
This can be modeled as a network flow problem where the source and target are Ougadougou and Timbuktu, the cities along the way are nodes, and each direct connection between two cities by train, bus, or plane is an edge. The actual flow problem to be solved is to:
a. Assign a total of capacity 3 to all outgoing edges from the source and find a feasible flow. b. Assign a total of capacity 3 to all incoming edges to the target and find a feasible flow. c. Assign each edge capacity 1 and check that the maximum flow is less than 3. d. Assign each edge capacity 1 and check that the maximum flow is at least 3.
3) A major political party’s main convention is currently in progress. The biggest 24-hour news channel in town wants full video coverage of all the major events. Unfortunately, some of these events overlap with each other. The channel’s program managers are trying to compute the minimum number of camera teams needed to cover all the relevant events.
The program managers decide to model this as a graph where the nodes are the major events to be covered, and edges represent pairs of events with overlapping timings. In this setting, the graph theoretic question to be answered is:
a. Find a spanning tree with a minimum number of edges. b. Find a minimum size decomposition into connected components. c. Find a minimal coloring. d. Find a minimum size vertex cover.
4) We wish to show that problem B is NP-complete. Which of the following facts is sufficient to establish this?
a. There is a polynomial-time reduction from B to SAT. b. There is a polynomial-time reduction from SAT to B. c. There is a polynomial-time reduction from B to SAT, and B has a checking algorithm. d. There is a polynomial-time reduction from SAT to B, and B has a checking algorithm.
5) We have constructed a polynomial-time reduction from problem A to problem B. Which of the following is a valid inference?
a. If the best algorithm for A takes exponential time, there is no polynomial-time algorithm for B. b. If we have a polynomial-time algorithm for A, we must also have a polynomial-time algorithm for B. c. If we don’t know whether there is a polynomial-time algorithm for B, there cannot be a polynomial-time algorithm for A. d. If the best algorithm for B takes exponential time, there is no polynomial-time algorithm for A.
