A new mathematical analysis reports sharply different complexity classifications for closely related ways of limiting vertex degrees in minimum spanning tree problems. Specified Degree MST and Bounded Degree MST are reported as fixed-parameter tractable, or FPT, when the input graph is parameterized by treedepth. Set of Degrees MST is reported as W[1]-hard under the combined parameter of treedepth and feedback vertex number, even for unweighted graphs in which each vertex has at most two admissible degree choices.
The comparison concerns three formulations of minimum spanning tree computation with local degree constraints. It is a formal study of algorithms and reductions on theoretical graph instances, not an experiment measuring how a particular software program performs.
The same basic task, different rules
The underlying task is to compute a minimum spanning tree while imposing conditions on the degree of each vertex. In the Set of Degrees MST formulation, an instance contains a graph, a function giving the permitted degree choices, and an edge-weight function. The analysis considers both weighted and unweighted constructions across the problem family.
The results use the language of parameterized complexity. Fixed-parameter tractable, or FPT, means that the analysis supplies an algorithmic tractability result controlled by the chosen structural parameter. W[1]-hard means that the analysis establishes a parameterized-hardness result under the stated parameter. These labels classify formal problem difficulty; they are not measurements of observed runtime or a claim that every individual instance is difficult.
Treedepth exposes a sharp divide
For Bounded Degree MST, the proof behind the treedepth result uses an integer linear program, or ILP, made up of integer variables and linear constraints. The construction is a well-structured ILP whose coefficients and dual-graph treedepth are bounded by a function of the input graph's treedepth, after which an FPT algorithm for that class of ILPs is applied. The analysis reports the resulting FPT classification for both Bounded Degree MST and Specified Degree MST under input-graph treedepth.
Set of Degrees MST does not receive the same positive classification under the combined treedepth and feedback-vertex-number parameter. The reported W[1]-hardness remains on unweighted graphs, with no vertex allowed more than two admissible degree values. The hardness construction reduces from Simple Multidimensional Partitioned Subset Sum, identified in the analysis as strongly W[1]-hard.
The contrast also appears under deletion distance, meaning the number of vertices that must be removed to reach a graph in a specified bounded-width class. Specified Degree MST is reported W[1]-hard when the target class has pathwidth at most 4 or treewidth at most 3, even on unweighted graphs. Set of Degrees MST is also reported W[1]-hard when the target class has pathwidth at most 4.
Vertex cover changes the result again
For unweighted graphs, Set of Degrees MST is reported as fixed-parameter tractable when the parameter is vertex cover number. The paper's algorithmic treatment transforms a modified Set of Degrees MST instance into a generalized B-matching problem.
The analysis also states an FPT result for weighted Set of Degrees MST, but under a combined parameter: vertex cover number together with the maximum size of an admissible-degree set. That qualification matters. The supplied results do not settle whether the general edge-weighted Set of Degrees MST problem is FPT by vertex cover number alone.
A map of formal difficulty, not a speed test
The authors interpret the split between the FPT and W[1]-hard classifications as a fundamental divergence among the three formulations on graphs of bounded treedepth, appearing specific to treedepth. Across the cases examined, the reported classifications differ by formulation and parameterization.
The evidence consists of theorem statements, ILP constructions, correctness arguments, parameterized reductions, and structural decomposition arguments. No empirical benchmark, dataset, or measured runtime comparison is reported, so the paper maps formal algorithmic difficulty rather than practical software speed.
The conclusions are limited to the problem variants, parameter combinations, graph restrictions, and admissible-degree conditions stated in the analysis. They do not classify every possible graph parameterization, remove the stated unweighted restrictions, or establish a blanket impossibility for every individual graph instance. The general edge-weighted vertex-cover case for Set of Degrees MST remains unsettled in the supplied analysis.
The work is still a preprint
The manuscript is identified in the supplied metadata as arXiv:2608.25530v1, dated 26 Aug 2026. It is an arXiv preprint.
Paper data and sources
Original title: Not All Degree Constraints Are Created Equal when Computing Spanning Trees
Authors: Narek Bojikian, Alexander Firbas, Robert Ganian et al.
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-26
DOI: Not available
Original paper · Full text