Florian Hörsch

activity

20202025

collaborators

8 papers

math.CO2025

Making an oriented graph acyclic using inversions of bounded or prescribed size

Jørgen Bang-Jensen, Frédéric Havet, Florian Hörsch +3

Given an oriented graph $D$ , the inversion of a subset $X$ of vertices consists in reversing the orientation of all arcs with both endpoints in $X$ . When the subset $X$ is of size…

cs.DM2025

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 $k$ -arc-connected orientation is particularly relevant in network design and reliability, as it guarantees robust communication between a designated set…

cs.DS2025

Odd and Even Harder Problems on Cycle-Factors

Florian Hörsch, Csaba Király, Mirabel Mendoza-Cadena +3

For a graph (undirected or directed), a cycle-factor is a collection of vertex-disjoint cycles covering the entire vertex set. Cycle-factors subject to parity constraints arise nat…

cs.CC2025

Maximum Reachability Orientation of Mixed Graphs

Florian Hörsch

We aim to find orientations of mixed graphs optimizing the total reachability, a problem that has applications in causality and biology. For given a digraph $D$ , we use $P (D)$ for…

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 $G$ , a set $T$ of terminal vertices, and a demand graph $H$ on $T$ , the \textsc{Multicut} problem asks for a set of edges of minimum weight that separates the pairs o…

math.CO2024

Matroid-reachability-based decomposition into arborescences

Florian Hörsch, Benjamin Peyrille, Zoltán Szigeti

The problem of matroid-reachability-based packing of arborescences was solved by Király. Here we solve the corresponding decomposition problem that turns out to be more complicated…

cs.DS2021

FPT algorithms for packing $k$ -safe spanning rooted sub(di)graphs

Stéphane Bessy, Florian Hörsch, Ana Karolinna Maia +2

We study three problems introduced by Bang-Jensen and Yeo [Theor. Comput. Sci. 2015] and by Bang-Jensen, Havet, and Yeo [Discret. Appl. Math. 2016] about finding disjoint "balanced…

math.CO2020

Connectivity of orientations of 3-edge-connected graphs

Florian Hörsch, Zoltán Szigeti

We attempt to generalize a theorem of Nash-Williams stating that a graph has a $k$ -arc-connected orientation if and only if it is $2 k$ -edge-connected. In a strongly connected digra…