Lab 2: NP-completeness reductions - the casting problem

This is a mandatory lab exercise that will give you one bonus credit on the exam if you pass the lab examination on April 12 2013 or before. You will get an extra bonus credit if you hand in correct solutions to the theory exercises below during the lab March 28. The lab work and the theory exercises should be solved individually or in pairs.

The person responsible for the casting in a film company needs to pair the right actor with the right roles. An actor may play multiple roles, but each role can only be played by one actor. The script specifies the roles that play in the same scenes. No monologues are allowed. Each actor may have only one role in each scene.

In addition the divas p1 and p2 are guaranteed roles in every casting. This means extra complexity, because the two do not tolerate each other, so the roles have to be cast in a way such that they never play against each other. The casting problem is to determine if all roles can be cast with the available actors. Input parameters hence are:
Roles r1, r2,... , rn
Actors p1, p2,... ,pk
Constraints of type 1 (for each role): rt can be played by p1, p2, p6
Constraints of type 2 (for each scene): in su the roles r1, r3, r5, r6 and r7 play

Input format

The first line of input consists of three integers: n, s and k (number of roles, number of scenes and number of actors, n≥1, s≥1, k≥2).
The following n lines represent the constraints of type 1 and begin with an integer indicating the number of subsequent integers on the line, followed by the numbers of the possible actors (between 1 and k, in boldface in the examples below).
The last s lines represent constraints of type 2. Each line begins with an integer indicating the number of subsequent integers on the line, followed by integers representing the different roles playing in that scene. Each role appears at most once in each row, so the number of roles is between 1 and n.

Question: Can the roles be cast by k actors so that p1 and p2 participate but not in the same scenes as each other?

Examples of valid input

negative instance:
5 5 3
3 1 2 3
2 2 3
2 1 3
1 2
3 1 2 3
2 1 2
2 1 2
3 1 3 4
2 3 5
3 2 3 5
       positive instance:
6 5 4
3 1 3 4
2 2 3
2 1 3
1 2
4 1 2 3 4
2 1 4
3 1 2 6
3 2 3 5
3 2 4 6
3 2 3 6
2 1 6 

Assignment

In this lab assignment you are going to show that the casting problem is NP-hard by reducing a known NP-complete problem, that is already implemented in Kattis. Your reduced instance will be tested and solved by Kattis. You can choose between reducing the following two problems: Graph Coloring (https://kth.kattis.scrool.se/problems/oldkattis:npreduction1) and Hamiltonian Cycle (https://kth.kattis.scrool.se/problems/oldkattis:npreduction2). The input format for these problems are defined below. Your task thus will be to implement a reduction, not to solve the casting problem!

Kattis will check whether your solution is correct, but you of course need to be able to prove it to be correct at the lab examination. The purpose of the answers of Kattis is to guide you in your work with the proof and point out if you forget an important special case. During the lab examination the teaching assistant will ask you why the problem is in NP and what the complexity of your reduction is.

Kattis uses a solver for (another) NP complete problem in order to test the correctness of your reduction. For technical reasons Kattis has a maximal allowed size of the instances. Kattis will tell you if you send too large an instance. If you can prove the correctness of your reduction you may be examined on the lab even if Kattis has not been able to check it completely.

GRAPH COLORING

Input: An undirected graph and a number of colors m. Isolated vertices and double edges may exist, but no loops.

Question: May the vertices of the graph be colored using at most m colors such that no neighbors have the same color?

Input format:
Line one: integer V (number of vertices, V≥1)
Line two: integer E (number of edges, E≥0)
Line three: goal m (max number of colors, m≥1)
One line for each of the E edges, consisting of the two endpoints of the edge (the vertices are numbered from 1 to V)

HAMILTONIAN CYCLE

Input: A directed graph.

Question: Is there a tour following edges in the graph and beginning and ending in the same vertex, passing each vertex in the graph exactly once?

Input format:
Line one: integer V (number of vertices, V≥1)
Line two: integer E (number of edges E≥0)
One line for each of the E edges, consisting of the start vertex and end vertex of the edge (the vertices are numbered from 1 to V)

Theory exercises

  1. Write, in any notation, a solution to the positive instance of the casting problem in the example above.
  2. Show that the casting problem is in NP.
  3. Modify the negative instance above to a positive instance. How many actors do you need to add in this case?
  4. Which is the smallest possible production that satisfies all input constraints for the casting problem and is possible to stage. Specify the input for this production.
  5. Imagine an instance where the roles are divided into two groups, in a similar manner as in the bipartite matching problem, and where each role never occurs in a scene together with another role from the same group. How many actors will be needed in this case?
  6. Suppose that an instance A contains a scene with the roles 4, 7 and 12, while the instance B has three scenes with the roles 4 and 7, 7 and 12, 4 and 12. If all other constraints are identical between the instances, will the solutions be identical? Why/why not?