I want to design fictional fruits that have three properties: color, taste and smell. There are $c$ possible colors, $t$ possible tastes and $s$ possible smells. Further, there is a feasibility matrix describing which colors go with which tastes and another feasibility matrix describing which tastes go with which smells. Together, these attributes form a three-way graph like the one shown in the picture below (here, there are 4 possible colors, 3 tastes and 5 smells). What is the minimum number of fruits I need to create so that all colors, all tastes and all smells are represented at least once? I need to devise an algorithm for this given the two connectivity matrices and prove its optimal.
EDIT: I asked a very similar question on CS stackexchange with some great answers. Check it out as well: https://cs.stackexchange.com/questions/131552/min-path-cover-for-a-three-layer-graph-with-all-paths-traversing-all-layers
My attempt:
I asked a similar question about colors and tastes. In that instances, a min edge cover was sufficient, with each surviving edge becoming one fruit. Now with three attributes, it becomes harder. One solution is to run one min-edge cover for colors and tastes and another for tastes and smells. Then, loop through the tastes and see if it has more colors connected to it or more smells connected to it. Assign fruits numbering the max of the two for that taste and assign each color and smell, repeating the one with smaller connections to that taste as required. This approach is almost certainly not optimal since there are multiple possible solutions for a min-edge cover and the two min-edge covers we ran had no knowledge of each other.
EDIT: here is a toy example demonstrating what we need. We have three colors, two tastes and three smells. The feasibility matrix is shown on the left while the optimal solution is shown on the right. We needed three fruits to cover all colors, tastes and smells. This also demonstrates that the "minimum path cover" algorithm referenced in the answer by Daniel below doesn't apply since it requires the paths to be "vertex-disjoint" i.e. not share any vertices. In the solution on the right, we see that the solution does indeed have two paths that share a vertex, $t_1$.
Best Answer
We may orient the edges in your "three-way graph" from colors to tastes and from tastes to smells to get a directed acyclic graph $D$. Then, as was noted in the comments, your problem is equivalent to finding a minimum path cover of $D$. This problem is NP-hard for general oriented graphs, but for DAGs it can be reduced to the problem of finding a maximum matching, as sketched here.
Minimum path covers in DAGs are also closely related to covering partially ordered sets with chains; the key result here is Dilworth's theorem, which describes the minimum number of chains required.
EDIT: Indeed, the link is only about vertex-disjoint path covers. Sorry about that! However, this can be fixed by the following observation. Given a DAG $D$, let $\widetilde{D}$ denote its transitive closure: it is a directed graph on the same vertex set as $D$, and for vertices $u,v \in V(D)$, there is a directed edge $uv$ in $\widetilde{D}$ if and only if there is a path $u \rightarrow v$ in $D$.
Now it turns out that there is a correspondence between path covers of $D$ and vertex-disjoint path covers of $\widetilde{D}$: for one, given a path cover of $D$, we can leave vertices from the paths so that the cover becomes vertex-disjoint, and the result will still be a path cover of $\widetilde{D}$. In the other direction, it is not difficult to see that a path in $\widetilde{D}$ can be augmented to a path in $D$ by inserting vertices. (This uses the assumption that $D$ was a DAG; for general directed graphs, we can only augment the path in $\widetilde{D}$ to a walk in $D$.) It follows that, given a path cover of $\widetilde{D}$, we can obtain a path cover of $D$ with the same number of paths, by augmenting each path separately.
Putting all these together, we have that the size of the minimum path cover of $D$, the size of the minimum path cover of $\widetilde{D}$, and the size of the minimum vertex-disjoint path cover of $\widetilde{D}$ are all the same. So we may indeed work with vertex-disjoint path covers.