Computing the degreewidth of a digraph is hard

Pierre Aboulker, Nacim Oijid, Robin Petit +2

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.…