NP-characterization of weightable digraphs
Informal Question (NP-characterization of weightable digraphs) · arXiv:2410.13008
Status partial medium confidence
Berger, Carter, and Seymour (arXiv:2601.12746, 2026) provide two hierarchical constructions: one that builds every planar weightable digraph from circular digraphs, and one that builds every weightable digraph from planar ones. Together these yield a structural construction for all weightable digraphs, substantially addressing the informal question, alongside a poly-time algorithm to test weightability. Whether this constitutes a full NP-characterization in the formal complexity sense (a polynomial-time verifiable certificate) is not explicitly confirmed in the abstract.
Cited literature (1)
-
Provides forbidden-subgraph characterization of weightable digraphs, a construction building every planar weightable digraph from circular digraphs, a construction building every weightable digraph from planar ones, and a poly-time algorithm to test weightability — collectively giving a structural construction for all weightable digraphs.
Reviewer notes. The follow-up paper arXiv:2601.12746 is co-authored by Seymour himself (the author of 2410.13008), suggesting it directly continues this line of research. The two-step hierarchical construction (all weightable from planar, all planar from circular) provides the sought construction for all weightable digraphs. The poly-time algorithm for testing weightability further suggests the complexity question may be fully resolved (P membership). The formal NP-characterization framing of the original question may be moot given the polynomial-time decidability result.
Context
A digraph $G$ is weightable if one can assign a real weight $w(e)$ to each edge $e$ such that $\sum_{e\in E(C)}w(e)=1$ for each directed cycle $C$. The paper shows weightability is characterizable by excluded subdigraphs (giving a co-NP characterization), but an NP-characterization via explicit construction remains open. For strongly 2-connected digraphs, Conjecture 1.2 would provide such a construction.
Notes. Stated as prose question in the introduction without a labelled environment.
Source paper
When all directed cycles have length three
Paul Seymour · 2025-02-09
https://arxiv.org/abs/2410.13008