Finding optimal sequence of questions to minimize total student time

Question

Suppose there is a tutorial session at a university. We have a set of $k$ questions $Q = \{ q_1 \ldots q_k \}$ and a set of $n$ students $S = \{ s_1 \ldots s_n \}$. Each student has a doubt in a certain subset of questions, i.e. for each student $s_j$, let $Q_j \subseteq Q$ be the set of questions that a student has a doubt it. Assume that $\forall 1 \leq j \leq n: Q_j \neq \phi$ and $\bigcup_{1\leq j\leq n}Q_j = Q$.

All students enter the tutorial session in the beginning (at $t = 0$). Now, a student leaves the tutorial session as soon as all the questions in which he has a doubt in have been discussed. Suppose that the time taken to discuss each question is equal, say 1 unit$^*$. Let $t_j$ be the time spent by $s_j$ in the tutorial session. We want to find out an optimal permutation $\sigma$ in which questions are discussed $(q_{\sigma(1)} \ldots q_{\sigma(n)})$ such the the quantity $T_\sigma = \Sigma_{1\leq j \leq n}t_j$ is minimized.

I have not been able to design a polynomial time algorithm, or prove $\mathsf{NP}$-hardness.

We can define a decision version of the problem $$ \mathsf{TUT} = \{\langle k, n, \mathcal{F}_Q, C \rangle \mid \exists \sigma : T_{\sigma} \leq C\} $$

where $\mathcal{F}_Q$ is the set of $Q_j$'s.

We can then find out the minimum $T_\sigma$ using binary search on $C$ and find out the optimal $\sigma$ using partial assignments to $\sigma$ in polynomial time using an oracle for $\mathsf{TUT}$. Also, $\mathsf{TUT} \in \mathsf{NP}$ because the optimal $\sigma$ can be used as a certificate which we can verify easily in polynomial time.

My question: Is $\mathsf{TUT}$ $\mathsf{NP}$-complete or can we design a polynomial time algorithm for it?

Sidenote: By the way, I thought of this question after an actual tutorial session, in which the TA discussed the questions in the normal order $q_1 \ldots q_n$ because of which many students had to wait until the end.

Example
Let $k=3$ and $n=2$. $Q_1 = \{q_3\}$ and $Q_2 = \{q_1, q_2, q_3\}$. We can see that an optimal $\sigma = \langle 3, 1, 2 \rangle$ because in that case, $s_1$ leaves after $t_1 = 1$ and $s_2$ leaves after $t_2 = 3$, so sum is 4.
However, if we discuss the questions in the order $\langle 1, 2, 3\rangle$, then $s_1$ and $s_2$ both have to wait till the end and $t_1 = t_2 = 3$, so sum is 6.

$^*$You are free to solve the more general case where each question $q_i$ takes $x_i$ units to discuss!

Answer 1

I suspect the problem $\mathsf{TUT}$ to be NP-hard. I will show how to transform the problem such that it is strongly related to a problem which is NP-hard. (Yes, this is all rather vague. I basically think my general approach is correct, but I am currently unable to proceed.)

First, note that the problem $\mathsf{TUT}$ can be reformulated as follows:

Given a set of questions $Q$ of size $k$, a set of $n$ subsets $\mathcal{F}_Q\subseteq \mathcal{P}(Q)$ and an integer $C$, does there exists a sequence $\Sigma : \langle S_1,\ldots, S_k\rangle$ such that, for all $i \in\{1,\ldots,k\}$:

1. $S_i\subseteq Q$ and $|S_i|=i$; and
2. $S_i \subset S_j$ for all $j>i$; and
3. $\sum_{i=1}^k |\{q\in\mathcal{F}_Q\mid q\not\subseteq S_i\}| \leq C$ ?

Note that the set $S_i$ represent the first $i$ questions that will be explained. Conditions 1 and 2 ensure that the subsets are well formed according to this interpretation. Condition 3 counts the amount of students that haven't left at every moment in time, so it indeed sums up to the total waiting time among all students.

Now, we restrict the size of the subsets in $\mathcal{F}_Q$ to $2$, so we can represent these subsets as edges on a graph where the vertices are the elements from $Q$. (A hardness result for this special case is sufficient for hardness of the general problem)

Now, the problem of minimizing $|\{q\in\mathcal{F}_Q\mid q\not\subseteq S_i\}|$ for a single $i$ (this is essentially ignoring condition 2) is equivalent to the following problem, which I dub '$\mathsf{\text{Double max $k$-vertex-cover}}$':

Given an undirected graph $G=(V,E)$ and integers $k$ and $t$, does there exist a set of vertices $V'\subseteq V$ of size at most $k$ such that the set $\{(u,v)\in E\mid u\in V' \wedge v \in V' \}$ has a size of at least $t$?

This problem is NP-hard, since $k$-clique is a special case of this problem, as this answer shows. However, this is not sufficient to prove $\mathsf{TUT}$ to be NP-hard, since we need to find the maximum for every $i$, while respecting condition 2. This conditions are not satisfied by every sequence $\Sigma$ that satisfies only condition 1 and 3: consider the graph on $7$ vertices with two disjoint cycles, one of size $4$, the other size $3$. For $i=3$, selecting all vertices in the $3$-cycle gives the maximum, while selecting all vertices of the $4$-cycle is optimal for $i=4$.

It seems that condition 2 makes the problem even harder and most certainly not easier, which means $\mathsf{TUT}$ should be NP-hard, but I haven't seen a method to formally prove this.

So, to summarize, I have reduced the question to the following:

• Is it possible to include condition 2 to complete the hardness proof for $\mathsf{TUT}$?

---

Side note: The formulation I gave makes it tempting to try an iterative algorithm which finds $|\{q\in\mathcal{F}_Q\mid q\not\subseteq S_i\}|$ under condition 2 from $i=1\ldots k$, by finding all maximum 'extenstions' of all found maximum sets for $i-1$. This does not lead to an efficient algorithm, as the amount of maximum sets at a single iteration may be exponential in $k$. Additionally, I have not seen a method to determine whether a subset for some $i$ would eventually become the 'global' maximum to prevent checking an exponential amount of subsets.