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
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 |
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)