pith. sign in

arxiv: 2407.19270 · v5 · submitted 2024-07-27 · 🧮 math.CO

Computing the degreewidth of a digraph is hard

Pierre Aboulker , Nacim Oijid , Robin Petit , Mathis Rocton , Christopher-Lloyd Simon This is my paper

Pith reviewed 2026-05-23 23:15 UTC · model grok-4.3

classification 🧮 math.CO
keywords degreewidthoriented graphNP-hardnessbackedge graphdigraph orderingcomputational complexitygraph parameter
0
0 comments X

The pith

It is NP-hard to decide whether an oriented graph has degreewidth at most 1.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that deciding if an oriented graph has degreewidth at most 1 is NP-hard, resolving an open question for this class of digraphs. Degreewidth is computed by finding an ordering of vertices that minimizes the highest degree in the backedge graph formed by arcs pointing backward in that order. Establishing hardness for the threshold of 1 completes the complexity picture for oriented graphs under this measure. The work also relates backedge-graph parameters to classical graph parameters in a broader discussion.

Core claim

We prove 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.

What carries the argument

Degreewidth of a digraph, the minimum over all vertex orderings of the maximum degree in the induced backedge graph.

If this is right

  • No polynomial-time algorithm exists for the degreewidth-1 decision problem on oriented graphs unless P equals NP.
  • The same decision problem remains hard when the input is restricted to oriented graphs rather than general digraphs.
  • Backedge-graph parameters stand apart from some classical ordering parameters in their computational behavior.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Similar hardness proofs might apply to deciding degreewidth at small constant values beyond 1.
  • The backedge-graph framework could be compared directly to parameters such as cutwidth or bandwidth through shared ordering techniques.

Load-bearing premise

A polynomial-time reduction exists from a known NP-hard problem to the question of whether an oriented graph has degreewidth at most 1, and the reduction preserves yes and no instances.

What would settle it

A polynomial-time algorithm that correctly answers whether every oriented graph has degreewidth at most 1 would disprove the hardness claim.

Figures

Figures reproduced from arXiv: 2407.19270 by Christopher-Lloyd Simon, Mathis Rocton, Nacim Oijid, Pierre Aboulker, Robin Petit.

Figure 1
Figure 1. Figure 1: Transfer digraph. Construction of the reduction. On a set of boolean variables X = {x1, . . . xn}, consider a 3-SAT formula φ = V 1≤j≤m Kj , where for 1 ≤ j ≤ m the clause Kj = (λ 1 j ∨ λ 2 j ∨ λ 3 j ) is a disjunction of literals λ i j for 1 ≤ i ≤ 3. To the formula φ, we associate a digraph D as follows. First to every clause Kj = (λ 1 j ∨ λ 2 j ∨ λ 3 j ) we associate a digraph Dj constructed as follows (… view at source ↗
Figure 2
Figure 2. Figure 2: Representation of a clause gadget. – If i = ij , then all out-arcs from ℓ ij j lead to ℓe ij j . Hence every path from ℓe ij j either contains (ℓe ij j , c ij j ) which is in F⊤ ⊆ F, or leads to ℓ i j for some i ̸= ij , and we are back to the previous point. In any case we proved that that E(C) ∩ F ̸= ∅. • If C is not included in any digraph Dj , then C goes through a transfer digraph from some ℓei j to so… view at source ↗
read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 0 minor

Summary. The paper proves that deciding whether an oriented graph has degreewidth at most 1 is NP-hard via a polynomial-time reduction, answering an open question of Keeney and Lokshtanov [WG 2024] and settling the last open case for oriented graphs. It also includes a general discussion relating backedge-graph parameters to classical digraph parameters.

Significance. If the reduction is correct, the result completes the complexity classification of degreewidth on oriented graphs and contributes to the study of ordering-based parameters defined via backedge graphs.

major comments (1)
  1. The central claim rests on a polynomial-time reduction establishing NP-hardness of degreewidth ≤1 on oriented graphs. The provided text (abstract and placeholder for full manuscript) supplies no construction, source problem, gadget details, or verification that the reduction (i) runs in polynomial time, (ii) produces an oriented graph, and (iii) preserves yes/no answers with respect to maximum degree of the backedge graph being at most 1.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for reviewing the manuscript and for identifying the need for explicit verification of the reduction. The full paper contains the complete construction and correctness argument in Section 3; the placeholder text supplied to the referee appears to have omitted those sections.

read point-by-point responses

  1. Referee: The central claim rests on a polynomial-time reduction establishing NP-hardness of degreewidth ≤1 on oriented graphs. The provided text (abstract and placeholder for full manuscript) supplies no construction, source problem, gadget details, or verification that the reduction (i) runs in polynomial time, (ii) produces an oriented graph, and (iii) preserves yes/no answers with respect to maximum degree of the backedge graph being at most 1.

    Authors: Section 3 of the full manuscript gives an explicit polynomial-time reduction from 3-SAT. Variable and clause gadgets are constructed so that the resulting digraph is oriented (no bidirectional arcs). The size of the constructed instance is linear in the size of the 3-SAT formula, establishing polynomial time. Correctness is proved by showing that the formula is satisfiable if and only if there exists an ordering whose backedge graph has maximum degree at most 1. We are prepared to expand any part of the argument or add a clarifying figure if the referee finds the current presentation insufficient. revision: no

Circularity Check

0 steps flagged

No circularity: NP-hardness via external reduction from known problem

full rationale

The paper proves NP-hardness of deciding degreewidth ≤1 on oriented graphs by polynomial-time reduction from an established NP-hard problem (answering an open question of Keeney and Lokshtanov). The abstract and description contain no self-definitional equations, fitted parameters renamed as predictions, load-bearing self-citations, uniqueness theorems imported from the same authors, or ansatzes smuggled via prior work. The cited reference is to a different group posing an open question, not a result by overlapping authors. The derivation chain is therefore self-contained against external benchmarks and receives the default non-finding.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper defines degreewidth from the backedge-graph construction but introduces no new free parameters or invented entities; the contribution is the hardness statement resting on standard complexity assumptions.

axioms (1)
  • standard math NP-completeness of the source problem used in the reduction
    Hardness proofs in graph theory rely on polynomial reductions from known NP-complete problems such as 3-SAT or vertex cover.

pith-pipeline@v0.9.0 · 5642 in / 1150 out tokens · 32217 ms · 2026-05-23T23:15:51.659940+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

17 extracted references · 17 canonical work pages

  1. [1]

    Four proofs of the directed Brooks’ Theorem.Discrete Mathematics, 346(11):113193, 2023

    Pierre Aboulker and Guillaume Aubian. Four proofs of the directed Brooks’ Theorem.Discrete Mathematics, 346(11):113193, 2023

    work page 2023

  2. [2]

    Clique number of tournaments

    Pierre Aboulker, Guillaume Aubian, Pierre Charbit, and Raul Lopes. Clique number of tournaments. arXiv preprint arXiv:2310.04265, 2023

    work page arXiv 2023

  3. [3]

    Finding forest-orderings of tournaments is NP- complete

    Pierre Aboulker, Guillaume Aubian, and Raul Lopes. Finding forest-orderings of tournaments is NP- complete. arXiv preprint arXiv:2402.10782, 2024

    work page arXiv 2024

  4. [4]

    Minimum acyclic number and maximum dichromatic number of oriented triangle-free graphs of a given order

    Pierre Aboulker, Frédéric Havet, François Pirot, and Juliette Schabanel. Minimum acyclic number and maximum dichromatic number of oriented triangle-free graphs of a given order. arXiv preprint arXiv:2403.02298, 2024

    work page arXiv 2024

  5. [5]

    Computing the clique number of tournaments

    Guillaume Aubian. Computing the clique number of tournaments. arXiv preprint arXiv:2401.07776, 2024

    work page arXiv 2024

  6. [6]

    Tournaments and colouring

    Eli Berger, Krzysztof Choromanski, Maria Chudnovsky, Jacob Fox, Martin Loebl, Alex Scott, Paul Seymour, and Stéphan Thomassé. Tournaments and colouring. Journal of Combinatorial Theory, Series B, 103:1–20, 01 2013

    work page 2013

  7. [7]

    The circular chromatic number of a digraph

    Drago Bokal, Gasper Fijavz, Martin Juvan, P Mark Kayll, and Bojan Mohar. The circular chromatic number of a digraph. Journal of Graph Theory, 46(3):227–240, 2004

    work page 2004

  8. [8]

    R. L. Brooks. On colouring the nodes of a network. Math. Proc. Cambridge Philos. Soc., 37:194–197, 1941

    work page 1941

  9. [9]

    P . Z. Chinn, J. Chvátalová, A. K. Dewdney, and N. E. Gibbs. The bandwidth problem for graphs and matrices—a survey. Journal of Graph Theory, 6(3):223–254, 1982

    work page 1982

  10. [10]

    Tournament immersion and cutwidth.Journal of Combinatorial Theory, Series B, 102(1):93–101, 2012

    Maria Chudnovsky, Alexandra Fradkin, and Paul Seymour. Tournament immersion and cutwidth.Journal of Combinatorial Theory, Series B, 102(1):93–101, 2012

    work page 2012

  11. [11]

    Degreewidth: A New parameter for Solving Problems on Tournaments

    Tom Davot, Lucas Isenmann, Sanjukta Roy, and Jocelyn Thiebaut. Degreewidth: A New parameter for Solving Problems on Tournaments. In International Workshop on Graph-Theoretic Concepts in Computer Science, pages 246–260. Springer, 2023

    work page 2023

  12. [12]

    Fomin and Michał Pilipczuk

    Fedor V . Fomin and Michał Pilipczuk. On width measures and topological problems on semi-complete digraphs. Journal of Combinatorial Theory, Series B, 138:78–165, 2019

    work page 2019

  13. [13]

    Exact and approxi- mate digraph bandwidth

    Pallavi Jain, Lawqueen Kanesh, William Lochet, Saket Saurabh, and Roohani Sharma. Exact and approxi- mate digraph bandwidth. In Arkadev Chattopadhyay and Paul Gastin, editors,39th IARCS Annual Confer- ence on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2019, December 11-13, 2019, Bombay, India, volume 150 of LIPIcs, pages 1...

    work page 2019

  14. [14]

    Degreewidth on semi-complete digraphs

    Ryan Keeney and Daniel Lokshtanov. Degreewidth on semi-complete digraphs. In International Workshop on Graph-Theoretic Concepts in Computer Science, page to be publisehd, 2024

    work page 2024

  15. [15]

    B. Mohar. Eigenvalues and colourings of digraphs. Linear Algebra and its Applications, 432(9):2273–2277, 2010

    work page 2010

  16. [16]

    The dichromatic number of a digraph

    Victor Neumann-Lara. The dichromatic number of a digraph. Journal of Combinatorial Theory, Series B , 33(3):265–270, 1982

    work page 1982

  17. [17]

    Some results and problems on tournament structure, 2023

    Tung Nguyen, Alex Scott, and Paul Seymour. Some results and problems on tournament structure, 2023. 9

    work page 2023