Showing 2025Show all
2 papers · 1 filter
cs.CC2025
Multicut Problems in Almost-Planar Graphs: The Dependency of Complexity on the Demand Pattern
Florian Hörsch, Dániel Marx
Given a graph , a set of terminal vertices, and a demand graph on , the \textsc{Multicut} problem asks for a set of edges of minimum weight that separates the pairs o…
cs.DS2025
From Chinese Postman to Salesman and Beyond II: Inapproximability and Parameterized Complexity
Fabian Frei, Ahmed Ghazy, Tim A. Hartmann +2
A well-studied continuous model of graphs considers each edge as a continuous unit-length interval of points. In the problem -Tour defined within this model, the objective to fi…