* 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 *p _{1}* and

Roles

Actors

Constraints of type 1 (for each role):

Constraints of type 2 (for each scene): in

The following

The last

Question:
Can the roles be cast by *k* actors so that
*p _{1}* and

Examples of valid input

negative instance:
5 5 3 3 |
positive instance:
6 5 4 3 |

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)

- Write, in any notation, a solution to the positive instance of the casting problem in the example above.
- Show that the casting problem is in NP.
- Modify the negative instance above to a positive instance. How many actors do you need to add in this case?
- 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.
- 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?
- 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?