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
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$.