BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Florian Hörsch

Florian Hörsch contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Discrete Mathematicsmath.CO

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
7works
0followers
2topics
1close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

7 published item(s)

preprint2022arXiv

Checking the admissibility of odd-vertex pairings is hard

Nash-Williams proved that every graph has a well-balanced orientation. A key ingredient in his proof is admissible odd-vertex pairings. We show that for two slightly different definitions of admissible odd-vertex pairings, deciding whether a given odd-vertex pairing is admissible is co-NP-complete. This resolves a question of Frank. We also show that deciding whether a given graph has an orientation that satisfies arbitrary local arc-connectivity requirements is NP-complete.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Globally balancing spanning trees

We show that for every graph $G$ that contains two edge-disjoint spanning trees, we can choose two edge-disjoint spanning trees $T_1,T_2$ of $G$ such that $|d_{T_1}(v)-d_{T_2}(v)|\leq 5$ for all $v \in V(G)$. We also prove the more general statement that for every positive integer $k$, there is a constant $c_k \in O(\log k)$ such that for every graph $G$ that contains $k$ edge-disjoint spanning trees, we can choose $k$ edge-disjoint spanning trees $T_1,\ldots,T_k$ of $G$ satisfying $|d_{T_i}(v)-d_{T_j}(v)|\leq c_k$ for all $v \in V(G)$ and $i,j \in \{1,\ldots,k\}$. This resolves a conjecture of Kriesell.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

On the complexity of finding well-balanced orientations with upper bounds on the out-degrees

We show that the problem of deciding whether a given graph $G$ has a well-balanced orientation $\vec{G}$ such that $d_{\vec{G}}^+(v)\leq \ell(v)$ for all $v \in V(G)$ for a given function $\ell:V(G)\rightarrow \mathbb{Z}_{\geq 0}$ is NP-complete. We also prove a similar result for best-balanced orientations. This improves a result of Bern\' ath, Iwata, Kir\' aly, Király and Szigeti and answers a question of Frank.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Reachability in arborescence packings

Fortier et al. proposed several research problems on packing arborescences. Some of them were settled in that article and others were solved later by Matsuoka and Tanigawa and by Gao and Yang. The last open problem is settled in this article. We show how to turn an inductive idea used in the latter two articles into a simple proof technique that allows to relate previous results on arborescence packings. We show how a strong version of Edmonds' theorem on packing spanning arborescences implies Kamiyama, Katoh and Takizawa's result on packing reachability arborescences and how Durand de Gevigney, Nguyen and Szigeti's theorem on matroid-based packing of arborescences implies Király's result on matroid-reachability-based packing of arborescences. Finally, we deduce a new result on matroid-reachability-based packing of mixed hyperarborescences from a theorem on matroid-based packing of mixed hyperarborescences due to Fortier et al.. In the last part of the article, we deal with the algorithmic aspects of the problems considered. We first obtain algorithms to find the desired packings of arborescences in all settings and then apply Edmonds' weighted matroid intersection algorithm to also find solutions minimizing a given weight function.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

A note on 2-vertex-connected orientations

We consider two possible extensions of a theorem of Thomassen characterizing the graphs admitting a 2-vertex-connected orientation. First, we show that the problem of deciding whether a mixed graph has a 2-vertex-connected orientation is NP-hard. This answers a question of Bang-Jensen, Huang and Zhu. For the second part, we call a directed graph $D=(V,A)$ $2T$-connected for some $T \subseteq V$ if $D$ is 2-arc-connected and $D-v$ is strongly connected for all $v \in T$. We deduce a characterization of the graphs admitting a $2T$-connected orientation from the theorem of Thomassen.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Connectivity of orientations of 3-edge-connected graphs

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 $2k$-edge-connected. In a strongly connected digraph we call an arc {\it deletable} if its deletion leaves a strongly connected digraph. Given a $3$-edge-connected graph $G$, we define its Frank number $f(G)$ to be the minimum number $k$ such that there exist $k$ orientations of $G$ with the property that every edge becomes a deletable arc in at least one of these orientations. We are interested in finding a good upper bound for the Frank number. We prove that $f(G)\leq 7$ for every $3$-edge-connected graph. On the other hand, we show that a Frank number of $3$ is attained by the Petersen graph. Further, we prove better upper bounds for more restricted classes of graphs and establish a connection to the Berge-Fulkerson conjecture. We also show that deciding whether all edges of a given subset can become deletable in one orientation is NP-complete.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Packing of mixed hyperarborescences with flexible roots via matroid intersection

Given a mixed hypergraph $\mathcal{F}=(V,\mathcal{A}\cup \mathcal{E})$, functions $f,g:V\rightarrow \mathbb{Z}_+$ and an integer $k$, a packing of $k$ spanning mixed hyperarborescences is called $(k,f,g)$-flexible if every $v \in V$ is the root of at least $f(v)$ and at most $g(v)$ of the mixed hyperarborescences. We give a characterization of the mixed hypergraphs admitting such packings. This generalizes results of Frank and, more recently, Gao and Yang. Our approach is based on matroid intersection, generalizing a construction of Edmonds. We also obtain an algorithm for finding a minimum weight solution to the above mentioned problem.

0 citations0 reviewsNo code linkedOpen access