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

• – D.W. Oct 31 at 21:08

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.

• Thanks! Why do you need the edge from $z$ to $a$? – Rohit Pandey Oct 25 at 19:40
• @RohitPandey, it's required in a circulation. (Alternatively, you could formulate this as an instance of a generalization of max flow where lower bounds are allowed, but that seems like a less standard problem, so I used a formulation as a circulation problem.) – D.W. Oct 25 at 22:18

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

• I think it would help to provide a proof of correctness for your proposed algorithm, i.e., a proof that the set of fruits it outputs is optimal. Some points that hopefully would be covered: How do you know that the optimum for each bipartite assignment, when combined, yield an optimum tripartite assignment? How do you do the combination? I don't understand how you use maximum matching to find an optimum bipartite assignment; if there is no perfect matching in the bipartite graph, what do you do then, and why is that optimal? – D.W. Oct 26 at 16:09
• @D.W. Maybe the term assignment is not relevant. Central and side layers play asymmetric roles as every central vertex is assigned to exactly one side vertex whereas side vertices may be assigned to zero or several central vertices. Building the tri-partite assignment (the fruits) is done by gathering for every central vertex, the left and the right vertices obtained in the bipartite assignments. The term "optimal" of the second step may be indeed misleading as it refers to "the tri-partite assignment that covers central layer and the most possible on both left and right layers." – Optidad Oct 26 at 16:23
• @Optidad Thanks, still trying to wrap my head around this. If you have time, it would help if you could demonstrate the working on the toy example in the question. – Rohit Pandey Oct 26 at 17:15
• @ Rohit Pandey, I elaborated a lot the method. Tell me if an example is still needed. – Optidad Oct 26 at 21:42
• I still don't see a proof of correctness for your method, nor anything that addresses the points that I raised above. I think you need a proof of correctness or some evidence that this outputs an optimal solution. Running time analysis is not enough; it's easy to come up with an algorithm that is fast but yields incorrect outputs. – D.W. Oct 27 at 2:22