This is a generalization of a variant of Doctor's Dilemma puzzle.
The general problem
Given an undirected connected graph $G$, one meeting is organized for each edge.
When two vertices meet each other, one or both can wear any number of available two-sided masks. All masks start out clean, but diseases spread from vertices and masks to vertices and masks, when they are in contact. Any mask can be safely inverted to swap its two sides.
We do not want to risk any vertex spreading (WLOG, its own unique) disease to any other vertex. What is the minimal number of masks that we need to order?
Given a graph $G$, is there an efficient way to find minimal number of masks $M(G)$?
Can we find exact solutions for $M$ for specific families of graphs?
Was a similar problem discussed before? I'm looking for references.
Lets represent a mask and its (inner, outer) contamination with $(I,O)$. Short notation $v$ for $\{v\}$ will be used for one element contamination. For example, $(v,\{u,w\})$ is contaminated by $v$ on inner side, by $u$ and $w$ on outer side.
Trivially $M(G)\lt |V|$, where $|V|$ is the number of vertices. If everyone meets with everyone and only $v_n$ doesn't wear a mask, all masks will end up as $(v_i,v_n),i=1,\dots,n-1$.
For example,
Given graph $K_{2,2}=C_4$, it is known that $M=2$.
Let vertices be $\{a_1,b_1,a_2,b_2\}$ and edges be $\{a_1b_1,a_2b_1,a_2b_2,a_1b_2\}$.
First, $a_1b_1$ meet by $a_1$ wearing a clean mask and $b_1$ wearing a clean mask (or equivalently, $a_1$ wears two clean masks stacked on each other while $b_1$ doesn't wear any masks). This results in masks $(a_1,\emptyset),(\emptyset,b_1)$.
Then, $a_1b_2$ meet by $a_1$ wearing the mask that they already contaminated, but $b_2$ does not wear any mask. At the same time, to meet $a_2b_1$, let $a_2$ wear clean side of mask contaminated by $b_1$. These two meetings result in masks $(a_1,b_2),(a_2,b_1)$.
Finally, $a_2b_2$ can meet, resulting in masks $(a_2,\{b_1,a_1\}),(\{a_1,b_1\},b_2)$.
We see that at every step, no vertices were contaminated by new diseases, as requested.
Notice that $M(G)\ge \left\lceil \frac{|V|}{2} \right\rceil$ where $|V|$ is the number of vertices of graph $G$, as every vertex will contaminate at least one side of some mask, which confirms that $M=2$ is optimal here.
Complete bipartite graphs
Can we solve the problem for $K_{n,n}$ graphs?
Let $a_i$ and $b_i$ be vertices in first and second set of bipartite graph.
When $n=1$ one mask is trivial, and $n=2$ is the previous example.
For $n\ge 3$, It is not hard to see $M(K_{n,n})\le n+\lfloor\frac{n}{2}\rfloor$, as:
- $a_i,i=1,\dots,\lfloor \frac{n}{2} \rfloor$ meet with $b_j,j=1,\dots,n$ by contaminating masks to $(a_i,\emptyset)(\emptyset,b_j)$.
- Next $a_x$ meets all $b_j$ using all masks of form $(\emptyset,b_j)$, contaminating them to $(a_x,b_j)$.
- Remaining $a_k,k\gt\frac{n}{2}$ meet all $b_j$ using inverted and stacked masks $(\emptyset,a_i),(a_x,b_j)$.
But, this is not optimal. (Also, step 2. is not needed when $n$ is even.)
This can be improved to: (see equivalent question on puzzling.SE)
$$M(K_{n,n})\le \left\lceil\frac{5n}{4}\right\rceil,$$
using a strategy that simulates $\frac{m}{2}$ new masks by stacking $m$ masks in pairs $(\emptyset,X),(Y,\emptyset)$, until about half of $a_i$ met with all $b_j$. Then, split $b_j$ into two groups and resolve remaining meetings.
Can we prove that this improvement is optimal?
Other families
Can we find both upper and lower bound for some common families?
E.g. In comments, someone asked about $K_{1,n}$. In this case, the lower bound stated at the end of first example can be achieved. Therefore, $M(K_{1,n})=\left\lceil \frac{n+1}{2} \right\rceil$.
E.g. meeting $3$ consecutive edges with $2$ masks in cycle $C_n$ gives $M(C_n)\le \left\lfloor \frac{2n}{3} \right\rfloor$.
E.g. what about complete $K_n$ graphs?
General algorithm
Can there exist an efficient algorithm for an arbitrary graph?
I can recognize three possible ways (moves) to meet some $v_i v_j$,
Contaminate both sides $(v_i, v_j)$ of a new mask $(\emptyset,\emptyset)$.
Contaminate a side $(v_i, v_j)$ of an existing mask $(v_i,\emptyset)$ or $(\emptyset,v_j)$.
Contaminate one side on one or both stacked masks $(v_i, X),(Y, v_j)$. This will result in masks $(v_i, X\cup Y),(X\cup Y, v_j)$, unless $(X, Y)$ exists to be placed in between.
This question then boils down to, is there a smart way to combine these moves?