Ferry cover with connectivity constraints
Programs & Events >

Ferry cover with connectivity constraints

Speaker: Umesh Shankar

General
  • Date 13 May 2026
  • Location CS36
  • Time 3:30 PM

Abstract

The classical Ferry Cover problem, inspired by Alcuin’s 8th-century river-crossing puzzles, asks for the minimum boat capacity required to transport the vertices of a graph across a river such that no edge is ever left alone on either bank. Formally, this requires that the banks always induce stable (independent) sets. In this talk, we present a generalization of this problem where the banks must satisfy an arbitrary graph property.
We first show that for any hereditary property—such as acyclicity or planarity—the structural characterizations of “small-boat” and “large boat” graphs extend directly from existing literature. Our primary focus then shifts to the connected-bank variant, a non-hereditary property where both banks must remain connected subgraphs throughout the entire transfer process.
Our main result is a complete structural characterization of boat-1 graphs which yields a linear-time recognition algorithm. Finally, we initiate the study of boat-n graphs for n ≥ 2, establishing tight bounds for stars and exploring algorithmic results for trees.

About the Speaker

Umesh Shankar is a Research Associate in Prof. Sunil Chandran’s Graph Theory and Combinatorics lab in the Department of Computer Science and Automation at IISc Bangalore. His research interests lie in Enumerative and Extremal Combinatorics. He completed his PhD from the Department of Mathematics at IIT Bombay, where his thesis study was on algebraic properties of polynomials arising in enumerative combinatorics under the supervision of Prof. Krishnan Sivasubramanian. Outside of his thesis study at IITB, he was a part of the Extremal Combinatorics research group headed by Prof. Niranjan Balachandran.

Image: Composite from Niranjan Balachandran, Ankita Dargad, Urban Larsson, Neeldhara Misra, and Umesh Shankar. "Ferry Cover with Connectivity Constraints". In 13th International Conference on Fun with Algorithms (FUN 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 366, pp. 6:1-6:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026) https://doi.org/10.4230/LIPIcs.FUN.2026.6