Min path cover for a three-layer graph with all paths traversing all layers

Question

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 "super-vertex" 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?

Answer 1

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.

Answer 2

Let's denote:

• $C$, the $c$ different colors,

• $T$, the $t$ different tastes,

• $S$, the $s$ different smells,

• $X$, the edges of the possible color/taste combinations,

• $Y$, the edges of the possible taste/smell combinations,

• $G((C, T, S), (X, Y))$, the tripartite graph of the problem.

FIRST STEP

Let's take the bipartite graph $G_L (C, T, X)$ containing colors and tastes (sub-graph of $G$). Let solve the following problem: find $t$ edges that cover all taste vertices and the maximum of color vertices.

For this use Hopcroft-Karp algorithm to get the maximum cardinality matching and complete with arbitrary edges for the unassigned taste vertices. Let's call $E_L$ this subset of $X$.

This step time complexity is $O(|X|\sqrt{max(c, t)})$.

SECOND STEP

Let's take the bipartite graph $G_R (T, S, Y)$ containing smells and tastes (sub-graph of $G$). Let solve the following problem: find $t$ edges that cover all taste vertices and the maximum of smell vertices.

As first step, use Hopcroft-Karp algorithm and complete arbitrarily to get $E_R$, subset of $Y$.

Now, gathering $E_L$ and $E_R$, you get $t$ fruits that cover $T$. Let's call $M_L$, the uncovered colors and $M_R$, the uncovered smells. Note that by construction, it does not exist $t$ other fruits that cover $T$ with lower $|M_L|$ or $|M_R|$.

This step time complexity is $O(|Y|\sqrt{max(t, s)})$.

THIRD STEP

If $M_L$ or $M_R$ is empty, just build arbitrary fruits that contain the element of respectively $M_R$ or $M_L$.

Else there is a max flow problem to solve. Let's create a source with edges to every element of $M_L$ and a sink with edges coming from every elements of $M_R$. All these edges have weight 1.

Use also all edges of $X$ (from $C$ to $T$) and $Y$ (from $T$ to $S$) with infinite weights.

In fact, we need the residual graph of all the fruits we already generated in previous steps. So for every fruit $(a, b, c)$ of $(C, T, S)$, put a "cancel edge" of weight 1 from $c$ to $b$ and from $b$ to $a$.

Now every augmenting path you find let you change your fruits to generate a new fruit that will cover both a color of $M_L$ and a smell of $M_R$.

When there is no more augmenting path, the remaining unassigned elements of $M_L$ and $M_R$ have to be covered with different arbitrary fruits.

This step time complexity using Ford-Fulkerson algorithm is $O((|X|+|Y|)min(|M_L|, |M_R|))$

PROOF

Following steps 1 and 2, by construction, the minimum number of fruits to cover $G_L$ (respectively $G_R$) is $t+|M_L|$ (respectively $t+|M_R|$). Then the minimum number of fruits $f_{opt}$ to cover $G$ and answer the problem follows:

$t + max(|M_L|, |M_R|) \le f_{opt} \le t + |M_L|+|M_R|$

Let's call $A_n$, the set of $n$ fruits that covers by priority the most elements in $T$, then in $C$, then in $S$. We denote $U(A_n) = (u_t, u_c, u_s)$, the number of vertices uncovered by $A_n$ in $(T, C, S)$. The solution of the problem is $A_{f_{opt}}$ such that $U(A_{f_{opt}}) = (0,0,0)$. As a new fruit can always be chosen to cover 1 element, while $n < f_{opt}$, $U(A_{n+1}) < U(A_n)$.

Note that for $n$ fruits, $A_n$ is not unique, for instance any fruit would work for $A_1$. Also, by construction, it exists at least one $A_{n-1}$ which is subset of $A_n$.

After step 2, by gathering $E_L$ and $E_R$ we obtain $A_t$ as the $t$ fruits fully cover $T$ and as much as possible of $C$ and $S$. $U(A_t) = (0, M_L, M_R)$.

Now in step 3, $n \ge t$, while there is an augmenting path, it let you build $A_{n+1}$ such that $U(A_{n+1}) = (0, u_c-1, u_s-1)$. Obviously, a new fruit cannot cover more that one color and one smell. If there is no augmenting path, it does not exist any $A_n$ that let you generate a new fruit covering both, one color and one smell. Thus, every new fruit will cover a single one of the remaining colors and smells and at this point $f_{opt} = n+u_c+u_s$.