NP-characterization of weightable digraphs
Informal Question (NP-characterization of weightable digraphs) · arXiv:2410.13008
Status solved medium confidence
Assuming the catalog's stated 2026 result is accurate, polynomial-time recognition puts weightability in P and hence in NP, while independently weightability is equivalent to admitting a 0–1 edge set meeting every directed cycle exactly once.
Cited literature (1)
-
Assuming the catalog's stated 2026 result is accurate, polynomial-time recognition puts weightability in P and hence in NP, while independently weightability is equivalent to admitting a 0–1 edge set meeting every directed cycle exactly once.
Reviewer notes. These status corrections report results attributed to existing papers or to the final source version. Graph-Theory-LLM-Proofs located and checked the implication; it is not credited as the author of the result. Audit caveat: The cited 2026 preprint and its bit-model algorithm were not independently checked, and its construction operations are not reproduced here.
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