15-351 / 15-650 / 02-613 Homework #6
Due: Friday, Dec. 4 by 11:59pm
You may discuss these problems with your current classmates, but you must write up your solutions indepen- dently, without using common notes or worksheets. You must indicate at the top of your homework who you worked with. Your write up should be clear and concise. You are trying to convince a skeptical reader that your answers are correct. Avoid pseudocode if possible. Your homework should be submitted via GradeScope as a typeset PDF. A LaTeX tutorial and template are available on the class website if you choose to use that system to typeset.
1. “Thom’s Problem.” On graduate school visit days, professors need to meet with visiting students to explain to them how great CMU is. Visiting students have certain professors they want to meet with and professors have certain visiting students they want to impress. Over visit day, there are meetings at various fixed time slots, and some professors and students are only available at certain times. Your task is to find an assignment of students, professors, and times that allows as many meetings to take place as possible.
More formally, we have:
• A set of visiting students S = {s1,…,sm}.
• A set of professors P = {p1,…,tn}.
• A set of time slots T = {t1,…,ta}.
• A collection of sets Api ⊆ T , where Api gives the time slots that professor pi is available.
• A collection of sets Asi ⊆ T , where Asi gives the time slots that student si is available.
• A collection of sets Mpi ⊆ S, where Mpi gives the students with whom professor pi is interested in meeting.
• A collection of sets Msi ⊆ P , where Msi gives the professors that visiting student si wants to meet.
Professor pi will only meet with students on her list Mpi and student si will only meet with professors on their list Msi . (We’ll relax these requirements later.) A meeting can only happen at time ti if both the student and professor are available. At any time, each student can meet with at most 1 professor and each professor can meet with at most 1 student.
Example input:
Professor Meeting Preferences:
Student Meeting Preferences:
Steve = MSteve Tom
Uri Wei Xin Yang Zhang
Everyone’s availability:
T
Prof. Abe = AAbe Prof. Bob
Prof. Carl
Prof. Dave
Steve = ASteve
Tom Uri Wei Xin Yang Zhang
S
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
Prof. Abe = MAbe Prof. Bob
Prof. Carl
Prof. Dave
P
1
Steve Tom Uri Wei Xin Yang Zhang
Prof. Abe Prof. Bob Prof. Carl Prof. Dave
2:00-2:30 2:30-3:00 3:00-3:30 3:30-4:00 4:00-4:30
(a) Write an integer linear program that finds maximum the number of (prof, student, time) meetings that can happen.
(b) Explain how to get the actual meeting schedule from your integer linear program.
(c) Suppose you are now also given, for each professor, a “bigshot score” bpi that is a positive number that says how important it is to satisfy that professor’s demands. For every meeting that professor pi takes with a student in her preference list Mpi , you get bpi points. Describe how to modify your integer linear program to find a schedule that maximizes the number of bigshot points your schedule gets.
For the following NP-completeness proof problems, you can only assume thatVertex Cover, Set Cover, In- dependent Set, 3-SAT, Hamiltonian Cycle, and Hamiltonian Path, Traveling Salesman Problem, which we discussed in class, are NP-complete.
2. Let Integer Linear Programming be the decision problem asking whether a given maximization inte- ger linear program has a solution of objective value ≥ a given k. Prove Integer Linear Programming is NP-complete.
3. A double-Hamiltonian traversal in an undirected graph G is a closed walk that goes through every vertex in G exactly twice.
Prove that the problem of testing whether a graph has a double-Hamiltonian traversal is NP-complete.
4. Suppose G = (V,E) is an undirected graph. A strongly independent set is a subset S of vertices such that for any two vertices u, v ∈ S there is no path of length ≤ 2 between u and v. Consider the following Strongly Independent Set problem: Given an undirected graph G = (V, E) and an integer k, does G have a strongly independent set of size k?
Prove that the Strongly Independent Set problem is NP-complete.
5. The Subgraph-Isomorphism Problem takes two undirected graphs G1 and G2 and asks whether G1 is a subgraph of G2. In other words, we ask whether there is an injective function f to map the vertices of G1 to the vertices of G2 such that there is an edge {u,v} in G1 exactly when {f(u),f(v)} is in G2.
Prove that Subgraph-Isomorphism Problem is NP-complete.
6. The Required Paths Subgraph problem takes as input an undirected graph G with nodes v1, . . . , vn, an n × n symmetric matrix R of natural numbers, and an integer b, and asks “Is there a set S of b edges of G with the following property: between every pair of nodes vi and vj, i ̸= j, there are at least Rij disjoint paths (that is, paths sharing no other node except for the endpoints) using edges in S.”
Prove that this problem is NP-complete.
2