3 papers
cs.DS2026
A Polynomial Kernel for Face Cover on Non-Embedded Planar Graphs
Thekla Hamm, Sukanya Pandey, Krisztina Szilágyi
Given a planar graph, a subset of its vertices called terminals, and , the Face Cover Number problem asks whether the terminals lie on the boundaries of at most $…
cs.DS2025
Planar Multiway Cut with Terminals on Few Faces
Sukanya Pandey, Erik Jan van Leeuwen
We consider the \textsc{Edge Multiway Cut} problem on planar graphs. It is known that this can be solved in time [Klein, Marx, ICALP 2012] and not in $n^{o(\sqrt{…
cs.DM2023
The Parameterised Complexity of Integer Multicommodity Flow
Hans L. Bodlaender, Isja Mannens, Jelle J. Oostveen +2
The Integer Multicommodity Flow problem has been studied extensively in the literature. However, from a parameterised perspective, mostly special cases, such as the Disjoint Paths…