Ferry Cover with Connectivity Constraints

For the lower bound, observe that during the first trip, the sailor must take at least $|Y|$ vertices so that the induced subgraph on the remaining vertices satisfies $P$. Thus $b_P\ge |Y|$.

For the upper bound, we exhibit a feasible schedule using a boat of size $|Y|+1$. The sailor keeps $Y$ on the boat permanently and transfers the remaining vertices one at a time using the one free seat. At any point during this process, both banks contain subsets of $V\setminus Y$. Since $G[V\setminus Y]$ satisfies $P$ and $P$ is hereditary, every induced subgraph of $G[V\setminus Y]$ also satisfies $P$. Hence $b_P\le |Y|+1$. $◀$

The following theorem generalizes Theorem 8 to arbitrary hereditary properties. The argument is very similar to the proof for the original setting, but we include it here for completeness.

We prove both directions separately.

Suppose subsets $X_1,X_2,X_3,Y_1,Y_2$ satisfying conditions (1)–(4) exist. We construct a feasible schedule, illustrated in Figure 2. We use the notation $L\mid B\mid R$ to denote a snapshot where $L$, $B$, and $R$ are the vertices on the left bank, boat, and right bank, respectively.

1. 1.

   Initial transport of $Y$: Load $Y$ onto the boat and deposit $Y_1$ on the right bank, then return. This yields $X\mid Y\setminus Y_1\mid Y_1$. This is valid since $|Y|\le b$, and both $X$ and $Y_1$ induce subgraphs satisfying $P$ (by conditions (1) and (3), using heredity).

2. 2.

   Transfer $X_{\mathrm{𝟏}}$: Since $Y_1\ne \mathrm{\varnothing }$, there is at least one free seat. Transfer elements of $X_1$ one by one from left to right, reaching $X_2\cup X_3\mid Y\setminus Y_1\mid Y_1\cup X_1$. Throughout, the left bank contains subsets of $X$ and the right bank contains subsets of $X_1\cup Y_1$, both satisfying $P$ by heredity.

3. 3.

   Exchange via $X_{\mathrm{𝟑}}$: Partition $X_3$ into $X_{31}$ and $X_{32}$ with $|X_{31}|\le |Y_1|$ and $|X_{32}|\le |Y_2|$ (possible by condition (4)). Execute four crossings:

   	$X_2\cup X_{32}$	$\mid (Y\setminus Y_1)\cup X_{31}\mid X_1\cup Y_1,$
   	$X_2\cup X_{32}$	$\mid Y\mid X_1\cup X_{31},$
   	$X_2\cup Y_2$	$\mid (Y\setminus Y_2)\cup X_{32}\mid X_1\cup X_{31},$
   	$X_2\cup Y_2$	$\mid Y\setminus Y_2\mid X_1\cup X_3.$

   At each step, both banks contain subsets of sets satisfying $P$, and the boat carries at most $b$ vertices.

4. 4.

   Transfer $X_{\mathrm{𝟐}}$: Since $Y_2\ne \mathrm{\varnothing }$, transfer elements of $X_2$ one by one, reaching $Y_2\mid Y\setminus Y_2\mid X$.

5. 5.

   Final transport: Load $Y_2$ and deposit everyone on the right bank.

Given a feasible schedule ${(L_k,B_k,R_k)}_{1\le k\le t}$, we construct the required subsets. We may assume $B_{k-1}\ne B_k$ for all $k$, since consecutive identical boat contents indicate redundant trips.

Let $Z$ be a smallest subset such that $G[V\setminus Z]$ satisfies $P$. By Observation 11, $|Z|\le b$. Let $Y$ be any superset of $Z$ with $|Y|=b$, and set $X=V\setminus Y$. Then $G[X]$ satisfies $P$. We consider three cases.

Set $Y_1=L_k\cap Y$, $Y_2=R_k\cap Y$, $X_1=L_k\cap X$, $X_2=R_k\cap X$, and $X_3=B_k\cap X$. Then $X_1,X_2,X_3$ partition $X$, satisfying (1). Both $Y_1$ and $Y_2$ are non-empty subsets of $Y$, satisfying (2). Since $L_k=X_1\cup Y_1$ and $R_k=X_2\cup Y_2$ must satisfy $P$ (as they are bank contents), condition (3) holds. For (4):

giving $|X_3|\le |Y_1|+|Y_2|$.

Suppose $k$ is even (the odd case is symmetric). Since $B_{k-1}\ne B_k=Y$, some vertices of $Y$ were on the right bank during trip $k-1$; set $Y_1=R_{k-1}\cap Y\ne \mathrm{\varnothing }$. Similarly, $B_{k+1}\ne Y$ implies $Y_2=L_{k+1}\cap Y\ne \mathrm{\varnothing }$.

Every vertex of $X$ lies in exactly one of $L_k$ or $R_k$. Define $X_1=R_{k-1}\cap X$, $X_2=L_{k+1}\cap X$, $X_{31}=B_{k-1}\cap X$, $X_{32}=B_{k+1}\cap X$, and $X_3=X_{31}\cup X_{32}$. Conditions (1)–(3) follow from the feasibility of the schedule. Since the sailor dropped $X_{31}$ and picked up $Y_1$ (filling the boat), we have $|X_{31}|\le |Y_1|$; similarly $|X_{32}|\le |Y_2|$, yielding (4).

Here, for all $k$, either $L_k\cap Y=\mathrm{\varnothing }$ or $R_k\cap Y=\mathrm{\varnothing }$, and $B_k\ne Y$ for . Since $L_1\cap Y\ne \mathrm{\varnothing }$ (initially all vertices are on the left) and $R_t\cap Y\ne \mathrm{\varnothing }$ (finally all are on the right), there must be some transition point. A careful analysis shows this contradicts the assumption that neither Case 1 nor Case 2 applies. $◀$

Since $H$ contains all edges of $G$, any subset of vertices inducing a connected subgraph in $G$ also induces a connected subgraph in $H$. Thus, any valid transfer schedule for $G$ remains valid for $H$. $◀$

If the graph has a Hamiltonian path, them we can remove consecutive vertices along the path. This leads to the following observation.

This observation prompts the question of whether Hamiltonian graphs are the only boat-1 graphs. It turns out that the answer is NO!

The graph in Figure 3 is biconnected – removing any single vertex leaves it connected. This observation leads to a key structural insight.

Using Lemma 34, we get $\widehat{S}$ of length $\widehat{t}$ from the given schedule $S$. The cost and demand of $\widehat{S}$ is not more than those of $S$, moreover, the boat set in each trip of $\widehat{S}$ is uniformly adjacent.

Let $\mathrm{\ell }$ be the first trip of $\widehat{S}$ whose boat set (${\widehat{B}}_{\mathrm{\ell }}$) is not bi-adjacent. The trips of $\widehat{S}$ after index $\mathrm{\ell }$ may also violate bi-adjacency. Hence, the total number of trips of $\widehat{S}$ that violate this property is at most $\widehat{t}-\mathrm{\ell }+1$.

We construct a new schedule $\overline{S}$ with the following properties:

1. 1.

   $\overline{S}$ is a legal schedule;

2. 2.

   The cost and demand of $\overline{S}$ is at most those of $\widehat{S}$; and

3. 3.

   The number of trips of $\overline{S}$ that violates the bi-adjacency is at most $\widehat{t}-\mathrm{\ell }$.

We then apply the same procedure to the new schedule. Since at each step the upper bound on the number of trips violating bi-adjacency strictly decreases, and the schedule has finite length, the process terminates after finitely many steps.

We now construct the new schedule. Let $\mathrm{\ell }$ be the first trip of $\widehat{S}$ that violates bi-adjacency. The construction of $\overline{S}$ is divided into multiple cases, depending on whether $\mathrm{\ell }$ is even or odd and boat set is adjacent to the left bank or the right bank.

Let ${\beta }^1$, ${\beta }^2,\mathrm{\dots },{\beta }^{\alpha }$ denote the connected components of ${\widehat{B}}_{\mathrm{\ell }}$, where $\alpha \ge 1$. Note that $\alpha$ cannot take the value 0, as otherwise ${\mathrm{\ell }}^{\text{th}}$ trip satisfy bi-adjacency. For pictorial representation of this case, refer to Figure 7. We further subdivide this case depending on what is dropped from the boat at the end of the ${\mathrm{\ell }}^{\text{th}}$ trip.

In this case, since ${\widehat{R}}_{\mathrm{\ell }+1}$ has some elements of ${\widehat{R}}_{\mathrm{\ell }}$, it cannot have any element of ${\widehat{B}}_{\mathrm{\ell }}$, otherwise ${\widehat{R}}_{\mathrm{\ell }+1}$ would be disconnected. This means ${\widehat{R}}_{\mathrm{\ell }+1}\subseteq {\widehat{R}}_{\mathrm{\ell }}$. Define a new schedule $\overline{S}$ as:

The schedule $\overline{S}$ is vacuously legal and

Hence, the cost and demand of $\overline{S}$ is at most those of $\widehat{S}$. Additionally, ${\mathrm{\ell }}^{\text{th}}$ trip of $\overline{S}$ satisfy bi-adjacency and therefore, the number of trips of $\overline{S}$ that violates bi-adjacency is at most $\widehat{t}-\mathrm{\ell }$.

In this case, either ${\widehat{R}}_{\mathrm{\ell }+1}=\mathrm{\varnothing }$ or ${\widehat{R}}_{\mathrm{\ell }+1}\cap {\beta }^i\ne \mathrm{\varnothing }$ for exactly one $i=1,2,\mathrm{\dots },\alpha$ as otherwise ${\widehat{R}}_{\mathrm{\ell }+1}$ would be disconnected. In the former case, ${\widehat{R}}_{\mathrm{\ell }+1}=\mathrm{\varnothing }$, define the new schedule as old schedule starting from $\mathrm{\ell }+2^{\text{th}}$ trip and it is easy to verify that the new schedule is legal, less costly and demanding than $\widehat{S}$ and the number of trips in new schedule is $\widehat{t}-\mathrm{\ell }$. In the later case, ${\widehat{R}}_{\mathrm{\ell }+1}\cap {\beta }^i\ne \mathrm{\varnothing }$ for $i=m$ (say), everything that was sent to the right bank before ${\mathrm{\ell }}^{\text{th}}$ trip is brought back in $\mathrm{\ell }+1^{\text{th}}$ trip, so to reduce the cost occurred in sending ${\widehat{R}}_{\mathrm{\ell }}$ is wasted. Hence, it would be better to start the schedule by sending just ${\beta }^m$ and then continue as per the further steps of the old schedule. So define the new schedule $\overline{S}$ as:

The schedule $\overline{S}$ is vacuously legal and the cost and demand of $\overline{S}$ as at most those of $\widehat{S}$ as

The $1^{\text{st}}$ trip of the $\overline{S}$ satisfy bi-adjacency, hence the total number of trips of $\overline{S}$ that violates bi-adjacency is at most $\widehat{t}-\mathrm{\ell }$.

Since ${\mathrm{\ell }}^{\text{th}}$ trip is the first trip to violate bi-adjacency, ${(\mathrm{\ell }-1)}^{\text{th}}$ trip satisfy bi-adjacency. This implies ${\widehat{B}}_{\mathrm{\ell }-1}\cup {\widehat{R}}_{\mathrm{\ell }-1}$ is connected as ${\widehat{R}}_{\mathrm{\ell }-1}$ is connected and ${\widehat{B}}_{\mathrm{\ell }-1}$ is adjacent to ${\widehat{R}}_{\mathrm{\ell }-1}$. Since, the schedule $\widehat{S}$ is legal, and $\mathrm{\ell }$ is even, ${\widehat{B}}_{\mathrm{\ell }}\cup {\widehat{R}}_{\mathrm{\ell }}={\widehat{B}}_{\mathrm{\ell }-1}\cup {\widehat{R}}_{\mathrm{\ell }-1}$. This implies, all CCs of ${\widehat{B}}_{\mathrm{\ell }}$ must be adjacent to ${\widehat{R}}_{\mathrm{\ell }}$, which contradicts the assumption.

The omit the details of the two cases one, when $\mathrm{\ell }$ is even and all CCs of $B_{\mathrm{\ell }}$ are not adjacent to ${\widehat{L}}_{\mathrm{\ell }}$ and other one, when $\mathrm{\ell }$ is odd and all CCs of $B_{\mathrm{\ell }}$ are not adjacent to ${\widehat{L}}_{\mathrm{\ell }}$, as they are similar to Cases 1 and 2.

This completes the proof. $◀$

In the next lemma, we show that given any optimal schedule, there exists another optimal schedule in which none of the vertices are ever transferred from the right bank to the left bank. To prove it, we use the following: In a schedule $S$ of $T$, if all the vertices are transferred only once, $C(S)=\mid V(T)\mid$ and vice-versa. This means, if $C(S)>\mid V(T)\mid$, there is at least one trip from the right bank to the left bank, in which the boat is non-empty. We rectify the last such trip and reduce the cost by not increasing the demand. Doing this repetitively gives an optimal schedule with $C(S)=\mid V(T)\mid$.

Among the set of optimal schedules (the ones minimizes the boat size) of $T$, let $S={(L_k,B_k,R_k)}_{1\le k\le t}$ be the one that minimizes the cost. Then by Lemma 36, there exists $\overline{S}={({\overline{S}}_k,{\overline{B}}_k,{\overline{R}}_k)}_{1\le k\le \overline{t}}$ such that $\overline{S}$ is optimal and $C(\overline{S})\le C(S)$. If the boat in all the return trips of $\overline{S}$ is empty, i.e., $C(\overline{S})=|V(T)|$, then we are done. Otherwise, assume $i$ is the first return trip of $\overline{S}$ in which the boat is non-empty, i.e., ${\overline{B}}_k=\mathrm{\varnothing }$ for all even and ${\overline{B}}_i\ne \mathrm{\varnothing }$.

By Lemma 36, ${\overline{B}}_{i-1}$ is adjacent to both ${\overline{L}}_{i-1}$ and ${\overline{R}}_{i-1}$ and ${\overline{B}}_i$ is adjacent to both ${\overline{L}}_i$ and ${\overline{R}}_i$.

If ${\overline{B}}_{i-1}\cap {\overline{B}}_i=\mathrm{\varnothing }$, all the vertices sent to right bank in $i-1^{\text{th}}$ trip stayed on the right bank and a subset of vertices from ${\overline{R}}_{i-1}$ were taken on the boat in the next trip, i.e., ${\overline{B}}_i\subseteq {\overline{R}}_{i-1}$. Since ${\overline{R}}_{i-1}$ is not adjacent to ${\overline{L}}_{i-1}={\overline{L}}_i$ (as otherwise it contradicts $T$ being a tree), ${\overline{B}}_i$ cannot be adjacent to ${\overline{L}}_i$, which is a contradiction. Hence, ${\overline{B}}_{i-1}\cap {\overline{B}}_i\ne \mathrm{\varnothing }$. Let $P={\overline{B}}_{i-1}\cap {\overline{B}}_i$, $X={\overline{B}}_{i-1}\backslash P$ and $Y={\overline{B}}_i\backslash P$. Then,

1. 1.

   $X\cap Y=\mathrm{\varnothing };$

2. 2.

   $X\subseteq {\overline{R}}_i$ and $Y\subseteq {\overline{R}}_{i-1}$ as $X\cup {\overline{R}}_{i-1}=Y\cup {\overline{R}}_i$.

We know ${\overline{B}}_i=P\cup Y$ is adjacent to ${\overline{L}}_i$. If $Y$ is adjacent to ${\overline{L}}_i={\overline{L}}_{i-1}$, then that implies ${\overline{R}}_{i-1}$ is adjacent to ${\overline{L}}_{i-1}$, which contradicts $T$ being a tree. Hence $P$ is adjacent to ${\overline{L}}_i={\overline{L}}_{i-1}$. Now consider the following schedule $S^{\prime }={(L_k^{\prime },B_k^{\prime },R_k^{\prime })}_{1\le k\le \overline{t}}$:

1. 1.

   All the trips of $S^{\prime }$ up to $i-2$ are same as those of $\overline{S}$,

2. 2.

   $L_{i-1}^{\prime }={\overline{L}}_{i-1}\cup P$,   $B_{i-1}^{\prime }=X$,   $R_{i-1}^{\prime }=R_{i-1}$,

3. 3.

   $L_i^{\prime }=L_{i-1}^{\prime }$,   $B_i^{\prime }=Y$,   $R_i^{\prime }=R_i$, and

4. 4.

   All trips of $S^{\prime }$ from $i+1$ to $\overline{t}$ is same as those of $\overline{S}$.

To show that $S^{\prime }$ is legal, we must show the following:

1. 1.

   $L_{i-1}^{\prime }=L_i^{\prime }$ is connected,

2. 2.

   $L_{i-1}^{\prime }\cup B_{i-1}^{\prime }={\overline{L}}_{i-1}\cup {\overline{B}}_{i-1}$,

3. 3.

   $B_{i-1}^{\prime }\cup R_{i-1}^{\prime }=B_i^{\prime }\cup R_i^{\prime }$, and

4. 4.

   $L_i^{\prime }\cup B_i^{\prime }={\overline{L}}_i\cup {\overline{B}}_i$.

Starting with item (1), since $P$ is adjacent to ${\overline{L}}_{i-1}$, $L_{i-1}^{\prime }$ and $L_i^{\prime }$ are connected each.

For item (2), we know $L_{i-1}^{\prime }\cup B_{i-1}^{\prime }={\overline{L}}_{i-1}\cup P\cup X={\overline{L}}_{i-1}\cup {\overline{B}}_{i-1}$.

For item (3), we know $B_{i-1}^{\prime }\cup R_{i-1}^{\prime }=X\cup R_{i-1}=Y\cup R_i=B_i^{\prime }\cup R_i^{\prime }$.

For item (4), we know $L_i^{\prime }\cup B_i^{\prime }={\overline{L}}_{i-1}\cup P\cup Y={\overline{L}}_i\cup {\overline{B}}_i$.

The cost of $S^{\prime }$ is strictly less than $C(\overline{S})$ and $D(S^{\prime })\le D(S)$, vacuously. This completes the proof of the claim. $\mathrm{⊲}$

This implies $S^{\prime }$ is an optimal schedule with lesser cost than $S$, which is a contradiction. Hence, the assumption about existence of $i$ such that ${\overline{B}}_i$ is non-empty is not true. This completes the proof. $◀$

Let $𝒮$ be the set of optimal schedules that have no non-empty backward trips and no empty forward trips such that it satisfies bi-adjacency. By Lemmas 36 and 38, we know that the set $𝒮$ is non-empty. We define a ordering on the schedules of the set $𝒮$ as follows: Define $S_1\le S_2$ if $\omega (S_1){\le }_{\mathrm{lex}}\omega (S_2)$ where ${\le }_{\mathrm{lex}}$ is the lexicographic ordering of positive integer sequences. We observe that the exclusion of non-empty backward trips and empty forward trips forces the sequences $\omega (S)$ for $S\in 𝒮$ to be in ${\mathbb{N}}_{\ge 0}^{2n}$ where $n=|V(T)|$. Since the lexicographic ordering on ${\mathbb{N}}_{\ge 0}^{2n}$ is a well-ordering, we can find a lexicographically minimal $\omega (S_0)$ for some $S_0\in 𝒮$.

We claim that $S_0={(L_k,B_k,R_k)}_{1\le k\le 2n}$ is the required schedule. By contradiction, assume that $S_0$ does not satisfy item (1) or $S_0$ is not the required schedule, then there exists a smallest $i$ such that $B_i$ has $u_i$ adjacent to $R_i$ and $v_i(\ne u_i)$ adjacent to $L_i$. Let $P$ be unique path on the tree $T$ from $u_i$ to $v_i$. Let $C_1,\mathrm{\dots },C_r$ be the connected components formed when $u_i$ is deleted from $B_i$ and adjust notation to let $v_i\in C_1$. We could break the forward trip $B_i$ into two smaller forward trips $B_i^{\prime }:=u_i{\cup }_{j=2}^r{C}_j$ and $B_i^{\prime \prime }:=C_1$ while keeping the other trips the same. It is a legal schedule as $v_i$ and hence $C_1$ is adjacent to $L_i$ and $C_2,\mathrm{\dots },C_r$ are all adjacent to $R_i$ in presence of $u_i$. This new schedule lies in $𝒮$ because it’s demand is no more than $D(S_0)$. Moreover, it’s weight sequence is lexicographically smaller than $S_0$, which is a contradiction. This proves our claim. $◀$

The following lemma follows directly from the definition of demand of a schedule.

We describe a tree transfer algorithm that works greedily.