6 papers
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…
On the minimum number of inversions to make a digraph -(arc-)strong
Julien Duron, Frédéric Havet, Florian Hörsch +1
The {\it inversion} of a set of vertices in a digraph consists of reversing the direction of all arcs of . We study (resp. ) whic…
Fixed-parameter tractability and hardness for Steiner rooted and locally connected orientations
Kristóf Bérczi, Florian Hörsch, András Imolay +1
Finding a Steiner strongly -arc-connected orientation is particularly relevant in network design and reliability, as it guarantees robust communication between a designated set…
Odd and Even Harder Problems on Cycle-Factors
Florian Hörsch, Csaba Király, Mirabel Mendoza-Cadena +3
For a graph (undirected, directed, or mixed), a cycle-factor is a collection of vertex-disjoint cycles covering the entire vertex set. Cycle-factors subject to parity constraints a…
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…
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 f…