Finding Degree-Constrained Acyclic Orientations

Jaroslav Garvardt, Malte Renken, Jannik Schestag, Mathias Weller

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review

5 Downloads (Pure)

Abstract

We consider the problem of orienting a given, undirected graph into a (directed) acyclic graph such that the in-degree of each vertex ν is in a prescribed list λ(ν). 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, which is known to be NP-hard in general, but polynomial-time solvable if no list λ(ν) contains large "gaps" [Cornuejols, J. Comb. Theory B, 1988]. In contrast, we show that deciding if an acyclic orientation exists is NP-hard even in the absence of such "gaps". On the positive side, we design parameterized algorithms for various, natural parameterizations of the acyclic orientation problem. A special case of the orientation problem with degree constraints recently came up in the context of reconstructing evolutionary histories (that is, phylogenetic networks). This phylogenetic setting imposes additional structure onto the problem that can be exploited algorithmically, allowing us to show fixed-parameter tractability when parameterized by either the treewidth of G (a smaller parameter than the frequently employed "level"), by the number of vertices ν for which |λ(ν)| ≥ 2, by the number of vertices ν for which the highest value in λ(ν) is at least 2. While the latter result can be extended to the general degree-constraint acyclic orientation problem, we show that the former cannot unless FPT=W[1].

Original languageEnglish
Title of host publication18th International Symposium on Parameterized and Exact Computation, IPEC 2023
EditorsNeeldhara Misra, Magnus Wahlstrom
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Number of pages14
ISBN (Electronic)9783959773058
DOIs
Publication statusPublished - 2023
Event18th International Symposium on Parameterized and Exact Computation, IPEC 2023 - Amsterdam, Netherlands
Duration: 6 Sept 20238 Sept 2023

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume285
ISSN (Print)1868-8969

Conference

Conference18th International Symposium on Parameterized and Exact Computation, IPEC 2023
Country/TerritoryNetherlands
CityAmsterdam
Period6/09/238/09/23

Keywords

  • General Factor
  • Graph Orientation
  • NP-hardness
  • Parameterized Algorithms
  • Phylogenetic Networks
  • Treewidth

Fingerprint

Dive into the research topics of 'Finding Degree-Constrained Acyclic Orientations'. Together they form a unique fingerprint.

Cite this