Is "meeting/room planning" NP-complete?

Question

Short summary: The problem is to assign people to meetings at different days while respecting the capacities and (inter-day) constraints of the meetings. Each person can only attend at most one meeting at a day.

I don't know if this problem has a common name - therefore the weird title question, sorry. If I overcomplicated any part of the problem definition, let me know.

People P = $\{p_1, .., p_n\}$, Meeting days D = $\{d_1, .., d_m\}$,

Meetings for each day: $M_{d_1} = \{m_{d_1,1}, .., m_{d_1,a}\}, M_{d_2} = \{m_{d_2,1}, .., m_{d_2,b}\}, .., M_{d_m} = \{m_{d_m,1}, .., m_{d_m,z}\}$
The $M_{d_i}$'s are pairwise disjoint.
Each meeting $m$ can hold a maximum number of people of $\text{cap}_{m}$ (capacity),

A person must not attend two (or more) meetings at different days that are "similar". (These conflicts are only between different days ("inter-day conflicts"). There are no conflicts within a day.)
Therefore define meeting constraints $C=\{c_1,..c_q\}$. Every meeting $m$ has exactly one corresponding constraint $c_i = \text{const}(m)$, s.t. [$\text{const}(m_i) = \text{const}(m_j)$] iff. [$m_i$ is "similar" to $m_j$] for all meetings.

There are preferences which person wants to attend which meeting at a particular day, e.g.:
(here 2 preferences are specified - if we generalize it to a fixed $K$ does the problem get any harder with regards to NP-hardness etc?)
$\text{Prefs} = \{$
$(p_1, \color{red}{d_1}, m_{\color{red}{d_1}, \color{green}{2}}, m_{\color{red}{d_1}, \color{green}{4}}),$ // Person 1 wants to attend the $\color{green}{2nd}$ or $\color{green}{4th}$ meeting at $\color{red}{day 1}$
$(p_1, d_3, m_{d_3, 1}, m_{d_3, 2}),$
$(p_3, d_2, m_{d_2, 2}, m_{d_2, 3}),$
$..$ $\}$, where:
a) every person-day combination $(p_i, d_j, ..)$ appears at most once.
b) every tuple has the form: $(p_i, \color{red}{d_j}, m_{\color{red}{d_j}, a}, m_{\color{red}{d_j}, b})$, with $a \neq b$ ($\widehat{=}$ valid preferences only)
(Note: The meeting preferences for each person-day combination are not supposed to be in any order, so (.., .., $x$, $y$) does not mean $x$ is preferred over $y$.)

A valid solution to the problem is:
Assign each person-day combination $(p_i, d_j, X, Y) \in \text{Prefs} $ to the meeting X or the meeting Y or no meeting at all, s.t.:
a) for every meeting $m$: we don't assign more people to $m$ than its capacity.
b) for every person $p$: for every constraint $c$: the person $p$ is assigned to (at most) one meeting with constraint $c$. (Otherwise, $p$ would attend two meetings at different days that are "similar".)

We want to maximize the number of person-day combinations that are assigned to a meeting. (So minimize the number of person-day combinations that are assigned to no meeting at all.)

Is this problem in $P$? (If yes, what is the idea for a polynomial-time algorithm?)
Is this problem NP-hard? (I tried a reduction from Bin-Packing $\leq_p$ ThisProblem, but without success. I think it's NP-hard and would appreciate any helpful ideas for reductions.)

Answer 1

While my initial instinct was also that the problem should be NP-hard, it looks like it might be close to a problem in P, namely list coloring on graphs whose blocks, or 2-connected components, are cliques. I am not sure to what extent this is helpful, because when you solve the reduced instance all meetings will be filled to capacity, which is an additional constraint on your problem. But if the rest of the argument holds up this might have workarounds, so I will state the partial progress.

If sensible, this reduction does not need to know which day a meeting happens to fall on, so I am using more relaxed notation (dropping the info about which day the meeting was on).

Introduce cap$_m$ vertices $$\{v_m^{(1)}, v_m^{(2)}, \ldots, v_m^{(c_m)}\}$$ for every meeting $m$. Let $M_r$ denote the set of all meetings $m$ that are associated with the constraint $c_r$. the edge set involves a big clique on all vertices involved in representing $m \in M_r$, that is, $$E = \{ (v_p^{(i)},v_q^{(j)}) | p,q \in M_r \}$$ $$\color{red}{\cup \{(v_p^{(i)}, v_q^{(j)})| p, q \text{ are meetings at the same day})\}\text{ [see comment below]} }.$$

The color pallette has one color for every person, and the list asssociated with a meeting vertex is the set of all people for whom the meeting is on their preference list.

A valid list coloring in the graph will fill all meetings to full capacity, and will never assign the same person to similar meetings, and will always give a person a meeting that they wanted to be in.

Some things to note:

1. The meetings will be filled to capacity, so this is not a completely accurate reduction. The simplest fix is to ask for a partial coloring, but I am not sure about the complexity of this question. One could make the same copies of every meeting an independent set, and add a complete partite structure across meetings with the same constraint. Now, the color corresponding to a person can be repeated within a meeting. However, I am not completely sure that the graph structure now allows for the Ptime algorithm! The other fix would be to introduce junk colors in the pallette, but then some people may not get assigned to meetings at all.

2. The reduction works with longer preference lists, too.

3. Conflicts within the same day can also be handled with this modelling.

And this paper mentions that list coloring can be resolved in polynomial time when the blocks of the graph are cliques.