Orienting Publications

Below you can find my publications and preprints on Finding Orientations of Phylogeneitc Networks, with links and toggleable abstracts.
To filter by a certain topic, click one of the buttons.

All FPT Food Webs Orienting Phylogenetic Diversity Phylogenetic Networks Scanwidth Implemented Algorithms

2023

[1]

conference paper

Finding Degree-Constrained Acyclic Orientations
Jaroslav Garvardt, Malte Renken, Jannik Schestag, and Mathias Weller

Proceedings of the 18th International Symposium on Parameterized and Exact Computation (IPEC 2023):19:1--19:14, 2023. conference TU Delft

We consider the problem of orienting a given undirected graph into an acyclic directed graph such that the in-degree of each vertex \(v\) is contained in a prescribed list \(\lambda(v)\). Variants of this problem have been studied for a long time and with various applications, but mostly without the requirement for acyclicity. Without this requirement, the problem is closely related to the classical General Factor problem. In contrast, we show that deciding whether an acyclic orientation exists is NP-hard even in the absence of large gaps in the degree lists. On the positive side, we design parameterized algorithms for various natural parameterizations. A special case of the problem recently arose in reconstructing evolutionary histories via phylogenetic networks. Exploiting this structure, we show fixed-parameter tractability when parameterized by the treewidth of the graph, by the number of vertices with multiple allowed indegrees, and by the number of vertices whose maximum allowed indegree is at least two.

@inproceedings{garvardt2023finding,
  title = {{Finding Degree-Constrained Acyclic Orientations}},
  author = {Garvardt, Jaroslav and Renken, Malte and Schestag, Jannik and Weller, Mathias},
  booktitle = {Proceedings of the 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
  pages = {19:1--19:14},
  year = {2023},
  organization = {Schloss-Dagstuhl-Leibniz Zentrum f{\"u}r Informatik},
  doi = {10.4230/LIPIcs.IPEC.2023.19}
}