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.