2026-09-24T16:39:37Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25725 2026-09-23T23:48:38Z ddc:004 open_access

Ferry Cover with Connectivity Constraints Balachandran, Niranjan Dargad, Ankita Larsson, Urban Misra, Neeldhara Shankar, Umesh ferry cover river crossing block-cut tree st-numbering hereditary graph property connectivity The classical Ferry Cover problem asks for the minimum boat capacity needed to transport all vertices of a graph across a river such that no edge remains on either bank at any time - a requirement that the banks induce stable (independent) sets. We study a natural generalization in which the banks must satisfy an arbitrary graph property. For hereditary properties such as acyclicity or planarity, we show that the structural characterization of small-boat and large-boat graphs established by Csorba, Hurkens, and Woeginger extends directly. We then turn to the connected-bank variant, where the property of interest - connectedness - is not hereditary: both banks must induce connected subgraphs throughout the transfer. We provide a complete characterization of graphs that can be transferred with a boat of size one (boat-1 graphs): a connected graph is boat-1 if and only if its block-cut tree is a path. This characterization yields a linear-time recognition algorithm. As a consequence, we show that every biconnected graph is boat-1, since such graphs admit an st-numbering. We also develop an efficient algorithm for determining the boat number of trees. Our work opens new directions for river-crossing problems under non-hereditary bank constraints. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Niranjan Balachandran and Ankita Dargad and Urban Larsson and Neeldhara Misra and Umesh Shankar 2026 Is Part Of LIPIcs, Volume 366, 13th International Conference on Fun with Algorithms (FUN 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FUN.2026.6 urn:nbn:de:0030-drops-257253 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2026.6 eng https://creativecommons.org/licenses/by/4.0/legalcode