Computing the degreewidth of a digraph is hard
Abstract
Given a digraph, an ordering of its vertices defines a backedge graph, namely the undirected graph whose edges correspond to the arcs pointing backwards with respect to the order. The degreewidth of a digraph is the minimum over all ordering of the maximum degree of the backedge graph. We answer an open question by Keeney and Lokshtanov [WG 2024], proving that it is \NP-hard to determine whether an oriented graph has degreewidth at most $1$, which settles the last open case for oriented graphs. We complement this result with a general discussion on parameters defined using backedge graphs and their relations to classical parameters.
Fields of Study & Subjects
Advanced Graph Theory Research
DNA and Biological Computing
Graph Labeling and Dimension Problems
Publication details
- Journal / source
- Discrete Mathematics & Theoretical Computer Science
- Volume
- vol. 28:2
- Issue
- Graph Theory
- Publication date
- 9 April 2026
- Language
- EN