2 papers
cs.DS2024
Hitting Meets Packing: How Hard Can it Be?
Jacob Focke, Fabian Frei, Shaohua Li +4
We study a general family of problems that form a common generalization of classic hitting (also referred to as covering or transversal) and packing problems. An instance of X-HitP…
cs.CC2023
Multicut Problems in Embedded Graphs: The Dependency of Complexity on the Demand Pattern
Jacob Focke, Florian Hörsch, Shaohua Li +1
The Multicut problem asks for a minimum cut separating certain pairs of vertices: formally, given a graph and demand graph on a set of terminals, the task…