Given a conflict graph G = (V, E), a man has to transport a set V of items/vertices across the river. Two items are connected by an edge in E, if they are conflicting and thus cannot be left alone together without human supervision. The available boat has capacity b ≥ 1, and thus can carry the man together with any subset of at most b items. A feasible schedule is a finite sequence of triples (L1, B1, R1), (L2, B2, R2), . . . , (Ls, Bs, Rs) of subsets of the item set V that satisfies the following conditions (FS1)–(FS3). The odd integer s is called the length of the schedule.
(FS1) For every k, the sets Lk, Bk, Rk form a partition of V . The sets Lk and Rk form stable sets in G. The set Bk contains at most b elements.
(FS2) The sequence starts with L1 ∪ B1 = V and R1 = ∅, and the sequence ends with Ls = ∅ and Bs ∪ Rs = V .
(FS3) For even k ≥ 2, we have Bk ∪ Rk = Bk-1 ∪ Rk-1 and Lk = Lk-1. For odd k ≥ 3, we have Lk ∪ Bk = Lk-1 ∪ Bk-1 and Rk = Rk-1.
Known Result: VertexCover(G) ≤ b ≤ VertexCover(G)+1.
Please help formulate this problem in MSO.