Min path cover for a three-layer graph with all paths traversing all layers Best to start with an example. I want to design fictional fruits. The fruits have three attributes: color, taste and smell. There are $c$ possible colors, $t$ possible tastes and $s$ possible smells. Further, there is a feasibility matrix between colors and tastes and also one between tastes and smells. Hence, this can be thought of as a tri-partite graph; but there are edge constraints only between successive layers and not between every combination of layers; so it is a special case of a tri-partite graph (in a general tri-partite graph, there would also be edges between colors and smells). My objective is to cover all possible colors, tastes and smells with a minimal number of fruits.
Included below is a toy example. Here, we have three colors, two tastes and three smells. The connectivity is as shown on the left. The optimal solution is shown on the right. We can see that there are three paths that can cover all possible colors, tastes and smells. Hence, three fictional fruits will suffice and are the minimal required (since there are three colors and smells, we couldn't have done it with less than three).

Note: Cross-posted here: https://math.stackexchange.com/questions/3878929/minimum-edges-required-to-cover-all-vertices-of-three-way-graph. See great answer there as well.

My attempt:
One algorithm that comes to mind is the minimal path cover for a DAG. However, the well known formulation of that problem requires the paths to not share any vertices. We can see in the solution above that this constraint only gets in our way for this problem. The optimal solution does indeed have two paths that share a common taste vertex ($t_1$). Hence, it doesn't immediately apply.
Another approach involves finding the min-edge cover for the bi-partite graph between colors and tastes and another min-edge cover between tastes and smells. Then, we can go to each taste and greedily assign colors and smells from the respective min-edge covers until everything is covered. This approach has a danger: the two min-edge covers are not aware of each other. In the figure below, the situation on the left shows one possible set of min-edge covers which leads to the optimal solution. But, we could also end up with the situation on the right. In that case, we'll end up needing four fruits to cover everything which is sub-optimal.

So, how do we fix the algorithm above? We want to encourage the behavior on the left from the min-edge cover and discourage the behavior on the right. We observe that $t_1$ is a &quot;super-vertex&quot; with more colors and smells attached to it. So, we can assign the edges emanating from it lower costs. Then, we can modify the min-edge cover algorithm to prefer the edges with low costs. One approach would be to take the minimum of the number of colors and smells attached to each taste and divide $1$ by this. Then all edges emanating from that taste get this as the cost.
This algorithm will work for our toy example. However, how do we prove its optimality in general? And if it isn't optimal, how do we devise an optimal algorithm?
I think this can be solved by reduction to a circulation problem.
Introduce a graph with source $a$ and sink $z$.  The edges are as follows:

All edges will have infinite capacity, lower bound 0, and cost 0 unless mentioned otherwise.
Add an edge $z \to a$ with cost 1.
Add edges $a \to c_i$ for each color $c_i$ and $s'_k \to z$ for each smell $s_k$.
For each allowable combination $c_i,t_j$, add an edge $c'_i \to t_j$, and each allowable combination $t_j,s_k$, add an edge $t'_j \to s_k$.
Add edges $c_i \to c'_i$, $t_j \to t'_j$, $s_k \to s'_k$ with lower bound 1.

Find the minimum cost solution to this circulation problem.  I think there exists an integral solution, and it can found in polynomial-time.
The solution corresponds to a collection of fruits, and the cost of the solution is the number of fruits required.  Each unit of flow corresponds to a fruit.  The structure of the graph ensures that each attribute is covered by at least one fruit.