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\geq 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 $(L\_1, B\_1, R\_1),\dots, (L\_s, B\_s, R\_s)$ 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 $L\_k, B\_k, R\_k$ form a partition of V . The sets $L\_k$ and $R\_k$ form stable sets in $G$. The set $B\_k$ contains at most $b$ elements.


(FS2) The sequence starts with $L\_1 \cup B\_1 = V$ and $R\_1 = \emptyset$, and the sequence ends with $L\_s = \emptyset$ and $B\_s\cup R\_s = V$.


(FS3) For even $k \geq 2$, we have $B\_k\cup R\_k = B\_{k-1} \cup R\_{k-1}$ and $L\_k = L\_{k-1}$. For odd $k \geq3$, we have $L\_k\cup B\_k= L\_{k-1}\cup B\_{k-1}$ and $R\_k = R\_{k-1}$.


Known Result: $VertexCover(G) \geq b \geq VertexCover(G)+1$.


Please help formulate this problem in MSO. 



Monadic Second Order (MSO) logic on graphs
Maybe there is a solution. But, for that I assume there is an upper bound in the number of rounds needed, say n, and that the value b is fixed upfront. Then, there is the following EMSO formula,


$\exists L\_{1} \exists B\_{1} \exists R\_{1} ... \exists L\_{n} \exists B\_{n} \exists R\_{n} \phi(L\_{1},B\_{1},R\_{1} ...,L\_{n},B\_{n},R\_{n})$ 


where $\phi = Seq\_{1} \wedge Seq\_{2} ...\wedge Seq\_{n}$ 


$Seq\_{1}$=$\forall x (XOR(x\in L\_{1},x \in B\_{1})) \wedge empty(R\_{1}) \wedge$ $lessthanb(B\_1) \wedge IndSet(L\_{1})$


If i is even :  

$Seq\_{i} = empty(L\_{i-1}) \vee (equals(L\_{i-1},L\_{i})\wedge 
\forall x ((x \in B\_{k-1} \vee x \in R\_{k-1})$
$ \Rightarrow XOR(x \in B\_{k},x \in R\_{k})))
\wedge lessthanb(B\_i) \wedge IndSet(L\_{i}) \wedge IndSet(R\_{i})$ 


If i is odd (i $\geq$ 3):   

$Seq\_{i}$ = $empty(L\_{i-1}) \vee (equals(R\_{i-1},R\_{i})\wedge \forall x ((x \in B\_{k-1} \vee x \in L\_{k-1})$
$ \Rightarrow XOR(x \in L\_{k},x \in B\_{k}))) \wedge lessthanb(B\_i) \wedge IndSet(L\_{i}) \wedge IndSet(R\_{i})$ 


$Seq\_{n} = empty(L\_{n-1})$


So if we can prove that if there is a solution then there is a solution of maximum n rounds which is dependent on the size of the graph then I think we have a solution.


empty(X) = $\forall x \neg(x\in X)$


lessthanb(X) = $\exists x\_{1} ... \exists x\_{b} (\wedge\_{i \neq j}\neg(x\_{i} = x\_{j})) \forall x (x \in X) \rightarrow (x=x\_{1} \vee... \vee x=x\_{b})$


IndSet(X) = $\forall x,y \in X \neg(R(x,y))$


