Pierre Aboulker ; Nacim Oijid ; Robin Petit ; Mathis Rocton ; Christopher-Lloyd Simon - Computing the degreewidth of a digraph is hard

dmtcs:14299 - Discrete Mathematics & Theoretical Computer Science, April 9, 2026, vol. 28:2 - https://doi.org/10.46298/dmtcs.14299
Computing the degreewidth of a digraph is hardArticle

Authors: Pierre Aboulker ; Nacim Oijid ; Robin Petit ; Mathis Rocton ; Christopher-Lloyd Simon

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.


Volume: vol. 28:2
Section: Graph Theory
Published on: April 9, 2026
Accepted on: February 25, 2026
Submitted on: September 18, 2024
Keywords: Combinatorics

Consultation statistics

This page has been seen 29 times.
This article's PDF has been downloaded 14 times.