{"id":"arxiv/2607.02619","url":"https://arxiv.org/abs/2607.02619","tags":["cs.DM","math.CO"],"score":0,"title":"Polynomial Algorithms for Minimum Degree Partitions in Semicomplete Digraphs","domain":"cs.DM","source":"arxiv","authors":["Hanzhi Bai","Jin Yan"],"reviews":0,"subject":"cs.DM","summary":"A 2-partition of a digraph is a partition of its vertex set into two nonempty parts. Degree-constrained 2-partition problems are generally computationally difficult, even when the prescribed properties are expressed only in terms of minimum indegree, minimum outdegree, or minimum semidegree. Bang-Jensen and Christiansen~\\cite{B-C} conjectured that the minimum-degree partition problems would be polynomial-time solvable on semicomplete digraphs when the degree thresholds are fixed, and Bang-Jensen and Gutin~\\cite{B-G-Classes} posed the related Problems~2.8.15 and~2.8.16. We resolve this…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-07-02","reactions":{}}