1
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ What did you try? $\endgroup$
    – Steven
    Apr 9, 2021 at 20:42
  • $\begingroup$ @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. $\endgroup$
    – Noice20
    Apr 9, 2021 at 20:49

1 Answer 1

1
$\begingroup$

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<j \le n$, 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$.

$\endgroup$
17
  • $\begingroup$ Thank you for your answer! However, why does it have to be k - 2 cycles and the weight divided by 2? $\endgroup$
    – Noice20
    Apr 9, 2021 at 21:02
  • $\begingroup$ 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$. $\endgroup$
    – Steven
    Apr 9, 2021 at 21:05
  • $\begingroup$ Okay, makes sense. Thank you! $\endgroup$
    – Noice20
    Apr 9, 2021 at 21:08
  • $\begingroup$ So if I got it right - if it is 3 cycles instead, we should add k - 3 "trivial" cycles or is it k - 2 always? $\endgroup$
    – Noice20
    Apr 9, 2021 at 21:12
  • 1
    $\begingroup$ $G$ gives you a cycle. For each additional cycle you need and extra vertex (and the corresponding two edges). $\endgroup$
    – Steven
    Apr 12, 2021 at 18:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.