5 papers · 1 filter
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 , the inversion of a subset of vertices consists in reversing the orientation of all arcs with both endpoints in . When the subset is of size…
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 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…
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 , we use for…
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…