Best algorithm for meeting scheduling optimization so that total number of held meetings is minimized

Question

Problem Description

I want to hold meetings where some given number of people will participate. They have some vacant dates respectively but they don't have the same date on which all of them can participate in the meeting. Therefore, I have to hold meetings multiple times so that all of them are able to participate at least a time. I want to reduce the number of meetings held to as few as possible.

For example, there are 4 participants $x_1, x_2, x_3, x_4$. They have their respective vacant dates:

• $x_1$ has $y_1, y_2$
• $x_2$ has $y_1, y_3$
• $x_3$ has $y_2$
• $x_4$ has $y_3$

In this case, holding meeting1 on $y_1$ where $\{x_1, x_2\}$ will participate, meeting2 on $y_2$ where $\{x_3\}$ will participates, and meeting3 on $y_3$ where $\{x_4\}$ will participates, is one of the possible solutions. However, the best solution is holding meeting1 on $y_2$ where $\{x_1, x_3\}$ will participate, and meeting2 on $y_3$ where $\{x_2, x_4\}$.

Problem Formulation

This problem can be formulated as follows: There are $N$ participants set $X = \{x_n\}_{n=1..N}$ and $M$ all possible dates set $Y = \{y_m\}_{m=1..M}$. Each participant $x_n$ has vacant dates $D_{x_n} \subseteq Y$ and $D_{x_n} \neq \emptyset$ respectively. I want to get the smallest partition $\mathcal{P} = \{P_i\}$ of $X$, e.g. $P_i \subseteq X, P_i \neq \emptyset, \bigcup_i P_i = X, P_i \cap{P_j} = \emptyset \ (i \neq j)$, that satisfy: $$\bigcap_{x_n \in P_i} D_{x_n} \neq \emptyset$$ In this notation, the optimization problem is formulated as: $$\min_{\mathcal{P}} |\mathcal{P}| \ s.t. \bigcap_{x_n \in P_i} D_{x_n} \neq \emptyset$$

I also noticed that this problem can be described as the problem on a bipartite graph with $\{x_n\} \in X$ and $\{y_m\} \in Y$ as nodes and $D_{x_n}$ can be converted into edges.

Question

• What is better algorithm than just selecting participants who can be grouped into existing groups in a forward order, which apparently produces non-optimal solution? (Off course, there is a brute force algorithm which seems computationally hard. I don't want such an algorithm)
• Is this problem NP hard?
• If you know, please teach me the name of the class of this type of problems.

Answer 1

From @RobPratt comment, I understood this problem is an instance of set cover problem.

The example in Problem Description above, can be viewed from the point of vacant dates instead of participants as:

• y_1 has x_1, x_2
• y_2 has x_1, x_3
• y_3 has x_2, x_4

Then this problem can be seen as selecting minimum subsets from all possible subsets $\{\{x_1, x_2\}, \{x_1, x_3\}, \{x_2, x_4\}\}$ such that $X = \{x_1, x_2, x_3, x_4\}$ is fully covered by selected subsets.

From Wikipedia

• This problem is an instance of set cover problem.
• This problem is NP-complete.
• There is a greedy algorithm with the approximation ratio, on each step selecting the subset which includes the largest number of uncovered elements.