# How to prove NP-completeness of this mail-problem?

Let's say we have n postmen that are bringing people mail in a neighbourhood, and that they start and end at the same post office. This situation can be decribed with a directed graph, where the vertices represent the people's houses the mails are brought to. If the graph has an edge from a to b, it means it is an accepted path to travel. Each postman must go from one house a to the next house b and cannot detour to a house c during that time. The post office manager says that a yes instance to this problem means that there exist n cycles so that

1. Each of the cycles contains a vertex x (represents the post office).
2. Every vertex except for x only appears once in each n cycle.
3. Each n cycle is of equal length.

The manager then wonders how to prove that this problem containing 3 cycles (3 equals n, so there are 3 postmen in this case) is a NP-complete problem?

Thank you.

• What did you try? Apr 9, 2021 at 20:42
• @Steven I was thinking of reducing the Hamiltonian cycle problem since it also requires to start and end with the same vertex, but then I'm not sure how to deal with the 3 cycles in the reduction and the part about every cycle being of the same length. Apr 9, 2021 at 20:49

Given an instance of partition $$X=\{x_1, x_2, \dots, x_n\}$$ you can build the graph $$G=(V,E)$$ where $$V=\{0, 1, \dots, n\}$$ and, for any pair of indices $$i$$, $$j$$ with $$0 \le i, there is an edge $$(i,j) \in E$$ of weight $$x_i$$. Additionally, $$E$$ contains all edges $$(i,0)$$ for $$1 \le i \le n$$ with weight $$0$$.
The deposit will be vertex $$0$$. If you are able to find two cycles $$C_1$$, $$C_2$$ of the same length then the sets $$\{x_i : i \ge 1 \wedge i \in C_1\}$$ and $$\{x_i : i \ge 1 \wedge i \in C_2\}$$ will be a partition of $$X$$. Similarly, a partition of $$X$$ induces two cycles of the same length in $$G$$.
This shows that the problem is $$\mathsf{NP}$$-hard even with just $$2$$ postmen. You can generalize this reduction to any number $$k$$ of cycles by adding $$k-2$$ additional vertices $$y_1, \dots, y_{k-2}$$ along with all edges $$(0, y_i)$$ of weight $$\frac{1}{2}\sum_{i=1}^n x_i$$ and $$(y_i, 0)$$ of weight $$0$$.
• In the case of $2$ cycles, the weight of each cycle is the weight of a set in a solution of the partition instance, i.e., it is $\frac{1}{2} \sum_i x_i$. If you want to find $k$ cycles, you can modify the reduction to add $k-2$ "trivial" cycles. Since the weight of each cycle must be the same, you want the additional $k-2$ cycles to also have weight $\frac{1}{2} \sum_i x_i$. These cycles are of the form $0 \to y_i \to 0$. Apr 9, 2021 at 21:05
• $G$ gives you a cycle. For each additional cycle you need and extra vertex (and the corresponding two edges). Apr 12, 2021 at 18:50