4 papers
Problems on Group-labeled Matroid Bases
Florian Hörsch, András Imolay, Ryuhei Mizutani +2
Consider a matroid equipped with a labeling of its ground set to an abelian group. We define the label of a subset of the ground set as the sum of the labels of its elements. We st…
The 3-dicritical semi-complete digraphs
Frédéric Havet, Florian Hörsch, Lucas Picasarri-Arrieta
A digraph is -dicritical if it cannot be vertex-partitioned into two sets inducing acyclic digraphs, but each of its proper subdigraphs can. We give a human-readable proof that…
Complexity results on the decomposition of a digraph into directed linear forests and out-stars
Florian Hörsch, Lucas Picasarri-Arrieta
We consider two decomposition problems in directed graphs. We say that a digraph is -bounded for some if each of its connected components contains at…
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…