Question

Consider the following scheduling problem. You are given a list of final exams $\mathit{F}\mathbf{1}\mathbf{,}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{,}\mathit{F}\mathit{k}$ to be scheduled, and a list of students $\mathit{S}\mathbf{1}\mathbf{,}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{,}\mathit{S}\mathit{l}$. Each student is taking some specified subset of these exams. You must schedule these exams into slots so that no student is required to take two exams in the same slot. The problem is to determine if such a schedule exists that uses only slots. Formulate this problem as a language and show that this language is$\mathit{N}\mathit{P}\mathbf{}\mathit{c}\mathit{o}\mathit{m}\mathit{p}\mathit{l}\mathit{e}\mathit{t}\mathit{e}$.

Short answer

The$SCHEDULE$ problem is also in$NP-complete$.

Step-by-step solution

Introduction

$F$as a certificate. It would then check each of the subsets of exams for the students, which are the members of $S$.

The algorithm for the verifier is $V$:

1. For each sublist of $S$, test if more than one exam lies in the same slot of $T$.

2. If yes, reject.

3. Test if all elements of $F$have a slot in $T$.

4. If no, reject.

5. Test if the number of slots used by $T$is more than$h$ .

6. If yes, reject. Else accept.

The steps $1,3and5$of the verifier$V$ all take polynomial time so the verifier takes polynomial time. Therefore, the language$SCHEDULE$ is in $NP$.

In the $h$Color Graph problem, the vertices of an undirected graph have to be colored in h colors such that for each and every edge $\left(u,v\right)$, the vertices $u$and $v$are colored differently. Later it will be proven that $h$the Color Graph problem is $NP-complete$.

Now, try to reduce all instances of the $h$Color Graph problem into instances of $SCHEDULE$in polynomial time.

Explanation

An instance of the $h$Color Graph problem with $\$k\{\backslash text\}${ vertices can be mapped to an instance }} $\$$of $\$SCHEDULE\{\backslash text\{with\left\}\right\}k\$$final exams and a maximum of$h$ slots taken by the schedule.

The lists of exams taken by the students are a subset of the set of the$k$ vertices. An edge between two vertices indicates a conflict, which is at least one student needs to take both exams.

This reduction can be performed in polynomial time. It is valid as:

If an instance of the$h$ Color Graph problem is true, then the instance of$SCHEDULE$ produced by the reduction will be true as exams (or vertices in the graph) colored identically can be scheduled in the same time slot and the length of the schedule will be time slots as there are different colors.

From an instance of the $SCHEDULE$problem, an instance of the$h$ Color Graph problem can be created. The vertices are created from the list of exams. Edges are drawn between vertices if at least a single student has to give both the related exams.

The vertices corresponding to exams in the same time slot are colored identically. This instance of the Graph Color problem is satisfied as only the vertices that do not lie in the same time slot can have edge between them and such vertices shall not have the same color.

Simplification

Now it needs to check which class of problems the Color Graph problem lies in. If it lies in $NP-complete$then the$SCHEDULE$ problem will also be in$NP-complete$ as the $NP-complete$class of problems is reducible in polynomial time to it.

The verifier for the h Color Graph problem will take the$\$C=\backslash left\backslash \{c\_\{1\},\backslash ldots,c\_\{k\}\backslash right\backslash \}\$$ colors assigned to the $\$N=\backslash left\backslash \{n\_\{1\},\backslash ldots,n\_\{k\}\backslash right\backslash \}\$$vertices as the certificate.

The algorithm for the verifier will be:

$V$= "On input$\$\backslash langle N, C\backslash rangle\$:$

1. Test if all the colors$C$ are valid.

2. If no, reject.

3. For each vertex$\$n\_\left\{i\right\}\$in\$N\$:$

Check if all adjacent vertices are colored differently.

4. If yes, accept; else reject.

The verifier takes polynomial time so the $h$Color Graph problem is in$NP$ . Following which, $NP-complete$problems have to be shown to be polynomial time reducible to the $h$Color Graph problem. The $hSAT$problem is reduced to the $h$Color Graph problem.

An instance of the $SAT$problem will haveclauses with each clause containing variables. The variable gadget will be the vertices of the graph labeled with the variables and the clause gadget will be the vertices (and their edges) added corresponding to them.

An instance of the Color Graph problem is constructed by adding all the variables and their complementsas vertices of the graph.

All the variable vertices are connected to their complements by an edge. Label the pair formed by a variable vertex and its complement as true for the variable and false for the complement.

Next, add a new set of vertices$\$x\_\left\{1\right\},\backslash ldots,x\_\left\{h\right\}\$$ to the graph in the form of a clique (by joining each new vertex with all the other new vertices). Color these vertices $\$x\_\left\{1\right\}, \backslash ldots, x\_\left\{h\right\}\$$with$\$c\_\left\{1\right\}, \backslash ldots, c \_\left\{h\right\}\$$ colors .

Also connect each$\$\{x\_\{i\left\}\right\}\$$ with $\$\{v\_\{j\left\}\right\}\$$and $\$\backslash overline\$\{v\_\{j\left\}\right\}\$$except for the case when $i=j$. Color one of $\$\{v\_\{j\left\}\right\}\$$or $\$\backslash overline\$\{v\_\{j\left\}\right\}\$$with the same color as the corresponding $\$\{x\_\{i\left\}\right\}\$$. This can be done with h+1 colors.

Thus, the$h$ Color Graph problem has been proven to be$NP-complete$ .

Consequently the$SCHEDULE$ problem is also in $NP-complete$.