Algorithms and Complexity of Generalized River Crossing Problems Hiro Ito1, Stefan Langerman2, and Yuichi Yoshida1,3 1 School of Informatics, Kyoto University, Kyoto 606-8501, Japan {itohiro,yyoshida}@kuis.kyoto-u.ac.jp 2 Maˆıtre de recherches du F.R.S.-FNRS, De´partement d’informatique, Universite´ Libre de Bruxelles (ULB), Belgium
[email protected] 3 Preferred Infrastructure, Inc. Abstract. Three men, each with a sister, must cross a river using a boat which can carry only two people, so that a woman whose brother is not present is never left in the company of another man. This is a very famous problem appeared in Latin book “Problems to Sharpen the Young,” one of the earliest collections on recreational mathematics. This paper considers a generalization of such “River-Crossing Problems.” It shows that the problem is NP-hard if the boat size is three, and a large class of sub-problems can be solved in polynomial time if the boat size is two. It’s also conjectured that determining whether a river crossing problem has a solution without bounding the number of transportations, can be solved in polynomial time even when the size of the boat is large. 1 Introduction 1.1 River Crossing Problems About Three Friends and Their Sisters: There were three men, each having an unmarried sister, who needed to cross a river. Each man was desirous of his friend’s sister. Coming to the river, they found only a small boat in which only two persons could cross at a time. How did they cross the river, so that none of the sisters were defiled by the men? [12] This is a very famous classic puzzle. It was appeared in “Propositiones ad Acuen- dos Iuvenes” (English: Problems to Sharpen the Young, translation from [7]), one of the earliest collections on recreational mathematics, written in Latin by medieval scholar Alcuin of York. The same book poses another river-crossing problem. The Wolf-Goat-Cabbage Problem: A certain man needed to take a wolf, a she-goat and a load of cabbage across a river. However, he could only find a boat which would carry two of these [at a time]. Thus, what rule did he employ so as to get all of them across unharmed? [7] E. Kranakis, D. Krizanc, and F. Luccio (Eds.): FUN 2012, LNCS 7288, pp. 235–244, 2012. c© Springer-Verlag Berlin Heidelberg 2012 236 H. Ito, S. Langerman, and Y. Yoshida One can find many variations of such “River-Crossing Problems” in various books on puzzles or recreational mathematics. In this paper, we consider a gen- eralized formulation of these problems. If the boat size is three, we show that finding the smallest solution is NP-hard. On the other hand, we show many sub-problems that can be solved in polynomial time if the boat size is two. We also conjecture that determining whether a river crossing problem has a solution without bounding the number of transportations, can be solved in polynomial time even when the size of the boat is large. 1.2 Definitions First we give a formulation of our problem: RIVER CROSSING INSTANCE: A set of drivers D, a set of customers C, a family of forbidden sets for the left bank FL ⊂ 2D∪C , one for the right bank FR ⊂ 2D∪C , one for the boat FB ⊂ 2D∪C , the size of the boat b ∈ Z+, the bound of the number of transportations T ∈ Z+ ∪ {∞}. QUESTION: Is there a way to transport all of the drivers and customers from the left bank to the right bank of a river using a boat under the following restrictions? RESTRICTIONS: 1. Initially all drivers, all customers, and the boat are on the left bank. 2. The capacity of the boat is b, i.e., it can transport at most b persons (drivers and customers) at a time. 3. Only drivers can operate the boat, i.e., at least one driver must be on the boat in any transportation. 4. It is forbidden to transport exactly the members of a forbidden set in FB in the boat. 5. It is forbidden to leave exactly the members of a forbidden set in FL (resp., FR) on the left bank (resp., the right bank). 6. The number of transportations is at most T . (Note: One way is counted as one transportation, i.e., a set of going and returning is counted as two transportations.) �unionsq For example, the Wolf-Goat-Cabbage Problem is formulated as follows: D = {Man}, C = {Wolf,Goat,Cabbage} FL = FR = {{Wolf,Goat}, {Goat,Cabbage}, {Wolf,Goat,Cabbage}}, FB = ∅, b = 2, T = ∞. Algorithms and Complexity of Generalized River Crossing Problems 237 Let P = D∪C, we call an element of P a person. In this paper, we assume every driver is allowed to operate the boat alone, in other words, FB never includes a singleton set of an element of D. (We call this model independent-driver model.) Note that T = ∞ doesn’t mean really infinite, i.e., if there is a schedule to move all persons to the right bank, we can do it in at most 2|P |+1 transportations. Because if a schdule requires more than 2|P |+1 transportations, it must come to the same state (who are on the left bank, who are on the right bank, and on which bank the boat is) twice. Clearly such a loop can be omitted and the schedule becomes shorter. That is, T = ∞ can be replaced by T = 2|P |+1. If b = 1, evidently the problem cannot be solved for |P | ≥ 2. Therefore we assume b ≥ 2. Another Formulation by Using ALLOWED SETS: Not too surprisingly, there is another way of defining the river crossing problem, by using “allowed sets” in place of forbidden sets. However in that case, the problem can be solved in polynomial-time, since it can be reduced to a shortest path problem on a graph whose vertices are the allowed sets. This approach would work well when faced with a problem in which the number of allowed sets is small. However, if the number of forbidden sets is small, then the number of allowed sets is exponentially large and this approach is no longer efficient. 1.3 Related Work There have been several attempts at analyzing this charming problem mathe- matically. In two articles from the 1960’s [2,10], methods are described to solve river crossing problems by building a graph whose vertices are the allowed sets, as mentioned in the previous section, and by computing a shortest path, or some other dynamic programming approach. More recently, several articles study generalized river crossing problems [1,4,5,8] in which the boat is operated by a unique driver, and a list of forbidden pairs of customers is provided. The goal is then to schedule the transportation in such a way that forbidden pairs cannot be in the same place without supervision from the unique driver. The problem is usually abstracted by a graph whose edge set is the forbidden pairs.The goal is then to compute theminimum capacity b of a boat such that the transportation of all people is possible. This problem is APX-hard [8] but canbe solved inO(4bnm) time,wheren andm are the number of vertices and edges, respectively, of the forbidden graph, i.e., it is FPT [4,5]. Our generalization is considerably more general than the previous ones. Main differences are as follows: 1. The number of drivers is exactly one in [1,4,5,8], but our formulation can treat any number of drivers. 2. Forbidden sets are given by pairs of customers in [1,4,5,8], but our formu- lation can treat any size of forbidden sets. As we will see in Section 2, this generalization is crucial as it makes the problem of finding the smallest so- lution NP-hard already when the size of the boat is 3. However, we show in 238 H. Ito, S. Langerman, and Y. Yoshida Section 3 that the generalization does not make the problem unmanageable as and give polynomial algorithms for a wide class of subproblems. 3. Our formulation separates the forbidden sets of banks and boats, i.e., FL, FR, and FB may be different. 2 Minimizing the Number of Transportations In this section we consider problems for minimizing T . If we use formulations of decision problems, any positive integer may be given for T . 2.1 NP-Hardness for Any Fixed b ≥ 3 Theorem 1. RIVER CROSSING is NP-hard even if FL = FR = ∅ and b is fixed to any integer greater than or equal to 3. We use the following problem, which is known to be NP-complete [6]. 3-DIMENSIONAL MATCHING (3DM) INSTANCE: A set M ⊆ W × X × Y , where W , X , and Y are disjoint sets having the same number q of elements. QUESTION: Does M contain a matching, that is, a subset M ′ ⊆ M such that |M ′| = q and no two elements of M ′ agree in any coordinate? Proof of Theorem 1: First we prove for the case of b = 3. Let (W,X, Y,M) is an instance of 3DM. We assume that q = |W | = |X | = |Y | is even. (Otherwise it is enough to add dummy elements w′ /∈ W , x′ /∈ X , y′ /∈ Y , and (w′, x′, y′) in W , X , Y , andM , respectively.) Give numbers to the elements ofW as {w1, . . . , wq}. We construct an instance (D,C,FB, T ) of RIVER CROSSING as follows. D = W ∪ {w0} (w0 /∈ W ), C = X ∪ Y, FB = {{p, p′, p′′} | p, p′, p′′ ∈ D ∪ C} −M − {{w0, w2i−1, w2i} | i ∈ {1, . . . , q/2}}, and T = 3q − 1. We prove the equivalence of them. (i) Assume that there is a matching M ′ ⊆ M . Let M ′ = {(wi, xi, yi) | i = 1, . . . , q} wlog. The way of a feasible transportation is as follows: All customers of X and Y are moved to the right bank by the following way: {w1, x1, y1} ∈ M ′ moves to the right bank, and w1 moves back to the left bank. {w2, x2, y2} ∈ M ′ moves to the right bank, and w2 moves back to the left bank. ... Algorithms and Complexity of Generalized River Crossing Problems 239 {wq, xq, yq} ∈ M ′ moves to the right bank, and wq moves back to the left bank. And all drivers, w0, w1, . . ., wq are moved to the right bank by the following way: {w0, w1, w2} moves to the right bank, and w0 moves back to the left bank. {w0, w3, w4} moves to the right bank, and w0 moves back to the left bank. ... {w0, wq/2−3, wq/2−2} moves to the right bank, and w0 moves back to the left bank. {w0, wq/2−1, wq/2} moves to the right bank. This process requires 3q − 1 transportations. (ii) Assume that there is a way to move them in at most 3q− 1 transportations. At most three persons can be moved from the left bank to the right bank at a time, and at least one person must be moved back from the right bank to the left bank when the boat returns. Thus the number of persons on the right bank increases at most two by a pair of going and returning (two transportations). By considering the last three persons can share the boat and they don’t need to back the boat to the left bank, we see that at most 3q+ 1 persons can be moved in T = 3q− 1 transportations. We have 3q+ 1 persons and thus three persons have to share in every transportation from the left bank to the right bank. From this, any customer in X and Y cannot move back from the right bank to the left bank. Consequently, the set of transportations including customers in X and Y must be a matching in M . Thus we proved that it is NP-hard if b = 3. For b > 4, the same proof works by separating each yi into b − 2 elements y1i , . . . , yb−2i and M is replaced by M∗ := {{w, x, y1i , . . . , yb−2i } | {w, x, yi} ∈ M}. �unionsq 2.2 Polynomially Solvable Problems with FL = FR = ∅ and b = 2 In Theorem 1, we show that RIVER CROSSING is NP-hard even if FL = FR = ∅ and b = 3. Here, we will show that it becomes polynomially solvable for independent-driver model with FL = FR = ∅ and b ≤ 2. From here we assume FL = FR = ∅ and b = 2. We construct a graph, called the allowed pair graph GA = (VA, EA), VA = P = D ∪ C EA = {(p, p′) | p ∈ D, p′ ∈ D ∪ C, p �= p′} − FB, i.e., an edge (p, p′) is in GA if and only if p and p′ can be transported by the boat at a time. Note that since at least one driver must be get on, for a pair of customers c, c′ ∈ C, (c, c′) cannot be in EA. GA can be obtained in polynomial time. If |D| = 1, i.e., there is only one driver, clearly all persons can be transported if and only if GA is a star graph of which the root is the unique element of D. There are |P | − 1 customers and one driver. Each customer except the final one 240 H. Ito, S. Langerman, and Y. Yoshida can move to the right bank by 2 transportations (a pair of going and returning) and the last customer and the driver can share the boat and move to the right bank by one transportation. It follows that the number of the transportations is 2(|P | − 2) + 1 = 2|P | − 3. Thus we assume that |D| ≥ 2. We first show the following simple observation (the proof is clear and omitted): Proposition 1. A customer c ∈ C that has no edge in GA can never be moved. Hence from here we assume that every customer has an edge between at least one driver. Let GD = (D,ED) is the sub graph of GA induced by D, i.e., GD is a graph showing pairs of drivers who can share the boat. Lemma 1. If |D| ≥ 2 and ED = ∅, then it is impossible to transport all persons even if T = ∞. Proof: Assume that there is a feasible schedule. Note that it is finished in at most 2|P |+1 transportations as mentioned in 1.2. Let d be the driver who finished to move lastly. (Note that d cannot share the boat with another driver since ED = ∅.) Let consider the turn such that all drivers but d have finished to move (and will never come back to the left bank). To move d, the boat must be back to the left bank. But clearly no driver cannot drive it from the assumption. �unionsq Now we show that if GA does not satisfy the above impossibility conditions of Proposition 1 and Lemma 1, all persons can be transported and the number of transportations required is also calculated by an simple expression as follows. Lemma 2. Assume that |D| ≥ 2, there is no singleton customer in GA, and ED �= ∅. Let s be the number of singleton drivers in GA. Then all persons can be transported in 2|P |+ 2s− 3 transportations, which cannot be decreased. Proof: Let δ1, . . . , δs be the singleton drivers and let D1, . . . , Dk be the connected components of GD −{δ1, . . . , δs}. From ED �= ∅, w.l.o.g we assume that there is a pair of drivers d1, d ′ 1 ∈ D1 such that (d1, d′1) ∈ ED. For i ∈ {2, . . . , k}, let di be an arbitrary driver in Di, and let (di, pi) be an arbitrary pair in EA including di (pi may be a customer). All persons except δ1, . . . , δs; d1, d ′ 1; d2, p2, . . . , dk, pk can be moved to the right bank by 2(|P | − s − 2k) transportations. (Since the number of such persons is |P | − s− 2k and two transportations are enough per one person.) We show that a pair (di, pi) (i = 2, . . . k) or δi (i = 1, . . . , s) can be moved to the right bank by 4 transportations, respectively, as follows. (1) (d1, d ′ 1) moves to the right bank. (2) d1 moves back to the left bank alone. (3) (di, pi) (or δi) moves to the right bank. (4) d′1 moves back to the left bank alone. Algorithms and Complexity of Generalized River Crossing Problems 241 By using this procedure, δ1, . . . , δs and d2, p2, . . . , dk, pk are moved to the right bank in 4s+4k− 4 transportations. Finally (d1, d′1) can be moved in one trans- portation. Consequently, the whole number of transportations is (2|P | − 2s− 4k) + (4s+ 4k − 4) + 1 = 2|P |+ 2s− 3. Next, we show this is the minimum. At most two persons can be moved from the left bank to the right bank at a time, and at least one person must be moved back from the right bank to the left bank when the boat returns. Thus, the number of persons on the right bank is increased at most one by a pair of going and returning (two transportations). By considering the last two persons can share the boat and they do not need to back the boat to the left bank, we can see that at least 2|P | − 3 transportations are required. If there is a singleton driver, he/she cannot share the boat, and hence one pair of going, which is driven by the singleton driver, and returning cannot increase the number of persons in the right bank. That is, one singleton driver increase the number of transportation at least two. Therefore, the number of transportations is at least 2|P | − 3 + 2s. �unionsq By combining the above discussions, we establish the followings. Theorem 2. On independent-driver model RIVER CROSSING, assume that b = 2 and FL = FR = ∅. If |D| = 1, then all persons can be transported if and only if there is no singleton customer in GA, and the minimum number of the transportations is 2|P |− 3. If |D| ≥ 2, then all persons can be transported if and only if there is no singleton customer in GA, and ED �= ∅; and the minimum number of the transportations is 2|P |+2s−3, where s is the number of singleton drivers in GA. Proof: Clear from Proposition 1 and Lemmas 1 and 2. �unionsq 3 Determining Reachability Only In this section we consider problems for determining reachability, i.e., the case with T = ∞. We obtained the following result. In the previous section, we consider the case with FL = FR = ∅. In this section, we allow any FL and FR. First we show the following result. Theorem 3. Assume that |D| = 1, b = 2, T = ∞, and FB = ∅. Then there is a polynomial time algorithm for determining whether or not all persons can be transported. Before considering this problem, we consider the following problem. Let Hn = (Vn, En) be the n-dimensional hypercube, i.e., Vn := {(x1, . . . , xn) | x1, . . . , xn ∈ {0, 1}} En := {(x, y) | x, y ∈ Vn and Ham(x, y) = 1}, where Ham(x, y) is the Hamming distance between x and y. 242 H. Ito, S. Langerman, and Y. Yoshida SUB-HYPERCUBE CONNECTIVITY INSTANCE: A dimension n ∈ Z+. A set of forbidden vertices F ⊆ Vn. QUESTION: Is there a path that doesn’t use any vertices in F starting from 0 = (0, . . . , 0) and destinating to 1 = (1, . . . , 1)? �unionsq We show the followings: Lemma 3. There is a polynomial time algorithm for SUB-HYPERCUBE CON- NECTIVITY. For solving the problem, we use the following idea. For a graph G = (V,E) and subsets of vertices S, T ⊆ V , E(S, T ) := {(s, t) ∈ E | s ∈ S, t ∈ T } and E(S) := E(S, V − S). The edge expansion of S of an n-regular graph G is h(S) := |E(S)| n ·min{|S|, |V − S|} and the edge expansion of G is h(G) := minS⊆V h(S). The following result has been known [11]. Lemma 4. h(Hn) = 1/n. Let Γ (S) := {t ∈ V − S | ∃s ∈ S s.t. (s, t) ∈ E}. Clearly n · |Γ (S)| ≥ |E(S)| for an n-regular graph. Proof of Lemma 3: If |F | < n, clearly there is no vertex cut Γ (S) ⊆ F separating 0 ∈ S and 1 ∈ V − S − Γ (S), then we assume |F | ≥ n. If there is such a cut Γ (S), then from the above discussions |Γ (S)| ≥ |E(S)| n = h(S) ·min{|S|, |V − S|} ≥ min{|S|, |V − S|} n . That is, we can say that if the connected component that includes 0 and the connected component that includes 1 are both larger than n|F |, then there is no vertex-cut separating 0 and 1, i.e., 0 and 1 is connected. From this, we obtain the following algorithm: It simply search (e.g., DFS) from 0. If the search finds a cut before reaching 1, it finds that the sub-hypercube is disconnected. If the search cannot find any cut in n|F |+ 1 steps (i.e., n|F |+ 1 vertices have been found in the connected component) without reaching 1, then it stops the search and starts another search from 1. If the second search finds a cut before reaching 0, it finds that the sub-hypercube is disconnected. If the search cannot find any cut in n|F |+1 steps without reaching 0, then it determines that it is connected. The correctness of this algorithm is supported by the above discussions, and the running time is O(n|F |). �unionsq By using the above algorithm, Theorem 3 is also proved. Algorithms and Complexity of Generalized River Crossing Problems 243 Proof of Theorem 3: Consider an instance I = (D = {δ}, C,FL,FR,FB = ∅, b = 2, T = ∞) of the problem of Theorem 3. Let |C| = c. We consider the c- dimensional hypercube Hc. For a vertex x = (x1, . . . , xc) of Hc, let C(x) := {i ∈ C | xi = 1} and C¯(x) := C−C(x). Regard each vertex x of Hc correspond- ing to a state, which is expressed as S(x), such that “C¯(x) ∪ {δ} and the boat are the left bank and C(x) is the right bank.” Let S′(x) be the state such that “C¯(x) are the left bank and C(x) ∪ {δ} and the boat is the right bank.” Note that S(0) is the initial state. Let consider the graph GI = (Vc, EI) such that EI = {(x, y) | x, y ∈ Vc, S(x) can be changed to S(y) by using two transportations.}. If “C¯(x) ∪ {δ} ∈ FL or C(x) ∈ FR,” then S(x) is forbidden, and if “C¯(x) ∈ FL or C(x) ∪ {δ} ∈ FR,” then S′(x) is forbidden. Thus we call a vertex x ∈ Vc is forbidden if C¯(x) ∪ {δ} ∈ FL, C(x) ∈ FR, C¯(x) ∈ FL, or C(x) ∪ {δ} ∈ FR. We will show that we can get to S(x) by a sequence of feasible transportations from the initial state if and only if there is a path from 0 to x in GI including no forbidden vertices. For proving this, it is enough to show that if S′(x) is forbidden, then we cannot get to S(x) from the initial state. The proof is as follows: To get to S(x), there must be a state S(y) such that |C(y)| = |C(x)|− 1 and there is a pair of going and returning of the boat that makes S(y) be S(x). Thus just the previous state of S(x) must be “C¯(x) is the left bank and C(x)∪{δ} is the right bank,” which is S′(x). Therefore if S′(x) is forbidden, we cannot get to S(x) from the initial state. Let G+I = (Vc, E + I ) be the graph obtained from GI by adding edges (x, y) such that x is forbidden and ∀y ∈ Vc. Reachability on G+I and GI are the same. From the previous observations, it follows that if y ∈ VI is not forbidden and (x, y) ∈ Ec, then (x, y) ∈ EI . Hence if (x, y) ∈ Ec, then (x, y) ∈ E+I . Therefore Ec ⊆ E+I . It follows that h(G+I ) ≥ h(Hc). From this, the algorithm for SUB- HYPERCUBE CONNECTIVITY given in the proof of Lemma 3 also works for G+I . �unionsq 4 Summary We give a formulation of a generalized river crossing problem and give some results on complexity on it. We proved that it is NP-hard even for FL = FR = ∅ if b = 3. On the other hand, we showed a polynomial-time algorithm for independent-driver model with b = 2 and FL = FR = ∅. 244 H. Ito, S. Langerman, and Y. Yoshida We also proved another subproblem with FL = FR �= ∅ that is in P (Theo- rem 3). The proof of it uses only that the expansion of the graph expressing the reachability of states is high. For many subproblems, such a graph seems hav- ing a big expansion, and hence, we conjecture that a wide subclass of RIVER CROSSING is in P even for b ≥ 3 if T = ∞. References 1. Bahls, P.: The wolf, the goat, and the cabbage: A modern twist on a classical problem, http://facstaff.unca.edu/pbahls/talks/WGC.pdf 2. Bellman, R.: Dynamic programming and “difficult crossing” puzzles. Mathematics Magazine 35(1), 27–29 (1962) 3. Borndo¨rfer, R., Gro¨tschel, M., Lo¨bel, A.: Alcuin’s transportation problems and integer programming, Preprint SC-95-27, Konrad-Zuse-Zentrum fu¨r Information- stechnik Berlin (1995) 4. Csorba, P., Hurkens, C.A.J., Woeginger, G.J.: The Alcuin Number of a Graph. In: Halperin, D., Mehlhorn, K. (eds.) ESA 2008. LNCS, vol. 5193, pp. 320–331. Springer, Heidelberg (2008) 5. Csorba, P., Hurkens, C.A.J., Woeginger, G.J.: The Alcuin number of a graph and its connections to the vertex cover number. SIAM J. Discrete Math. 24(3), 757–769 (2010) 6. Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman And Company (1979) 7. Heeffer, A.: Alcuin, http://logica.ugent.be/albrecht/alcuin.pdf 8. Lampis, M., Mitsou, V.: The Ferry Cover Problem. In: Crescenzi, P., Prencipe, G., Pucci, G. (eds.) FUN 2007. LNCS, vol. 4475, pp. 227–239. Springer, Heidelberg (2007) 9. Peterson, I.: Tricky crossings, Science News Online 164(24), http://web.archive.org/web/20040603203306 , http://www.sciencenews.org/articles/20031213/mathtrek.asp (retrieved February 7, 2008) 10. Schwartz, B.R.: An analytic method for the “difficult crossing” puzzles. Mathe- matics Magazine 34(4), 187–193 (1961) 11. Trevisan, L.: Graph Partitioning and Expanders, Stanford University — CS359G, Lecture 6 (2011), http://theory.stanford.edu/~trevisan/cs359g/ 12. Propositiones ad Acuendos Juvenes, Wikipedia, the free encyclopedia Algorithms and Complexity of Generalized River Crossing Problems Introduction River Crossing Problems Definitions Related Work Minimizing the Number of Transportations NP-Hardness for Any Fixed b 3 Polynomially Solvable Problems with FL = FR = and b = 2 Determining Reachability Only Summary References