PaperlayerView exact revision on arXiv

Source-linked AI summary

Not All Degree Constraints Are Created Equal when Computing Spanning Trees

Narek Bojikian, Alexander Firbas, Robert Ganian, Hung P. Hoang, Krisztina Szilagyi

arXiv:2608.25530v1cs.DS

TL;DR

The paper studies minimum-cost spanning trees with prescribed local degree constraints and examines their complexity under restrictive graph parameters. It establishes tractability for bounded-degree instances by treedepth, contrasts this with hardness for set-valued degree constraints, and gives a vertex-cover-based tractability result.

  • Problem

    The paper asks how minimum-cost spanning-tree problems with local degree constraints behave under restrictive structural parameters.

  • Method

    The paper develops parameterized algorithms and hardness reductions, including a reduction from Set of Degrees MST to generalized B-matching.

  • Results

    Bounded Degree MST is fixed-parameter tractable by treedepth, while Set of Degrees MST is W[1]-hard by treedepth plus feedback vertex number; Set of Degrees MST is also FPT by vertex cover plus maximum admissible-set size.

  • Takeaways & Limitations

    The results show that degree-constraint formulations can have different parameterized complexity under restrictive graph parameters.

  • Takeaways & Limitations

    Whether Set of Degrees MST is fixed-parameter tractable by vertex cover alone for general edge-weighted graphs remains open.

Abstract

from arXiv · show

We study the computation of minimum spanning trees subject to local degree constraints. Recent work (ICALP 2026) established that three natural formalizations of this problem share the exact same parameterized complexity under standard structural graph parameters, including treewidth, pathwidth and clique-width. This applies to the cases where every vertex has a single target degree (Specified Degree MST), or a degree upper bound (Bounded Degree MST), or is equipped with a set of admissible degrees (Set of Degrees MST). In this paper, we investigate these problems under more restrictive parameterizations and reveal that their complexity landscapes fundamentally diverge on bounded-treedepth graphs. Specifically, we prove that the former two problems are fixed-parameter tractable when parameterized by the treedepth of the input graph. In sharp contrast, we show that Set of Degrees MST remains W[1]-hard parameterized by treedepth, even when combined with the feedback vertex number (i.e., deletion distance to treewidth $1$). Finally, we show that this divergence seems to be specific to treedepth: we exclude an analogous W[1]-hardness result for Set of Degrees MST w.r.t. the vertex cover number and also rule out fixed-parameter algorithms for the former two problems w.r.t. deletion distance to constant pathwidth.

1 Introduction

The paper revisits degree-constrained minimum spanning trees under stronger structural parameters and finds that treedepth separates the complexity of the three variants. It establishes tractability for Bounded and Specified Degree MST, hardness for Set of Degrees MST under treedepth-based parameters, and contrasting results for vertex cover and bounded-width deletion.

  • Problem setting: Degree-constrained MST asks for a minimum-cost spanning tree whose vertex degrees satisfy prescribed local requirements.The three variants differ by allowing arbitrary admissible-degree sets, upper bounds, or singleton target degrees.
  • Prior landscape: Earlier work found identical parameterized complexity for Specified, Bounded, and Set of Degrees MST across treewidth, pathwidth, and clique-width.Its lower bounds applied to Specified Degree MST, while its upper bounds handled the more general Set of Degrees MST.
  • Treedepth perspective: Treedepth is a stricter structural parameter than treewidth because bounded-treedepth graphs exclude long paths.The paper uses treedepth as a measure of recursive vertex-elimination depth and graph closeness to a star forest.
  • Treedepth results: Bounded Degree MST is fixed-parameter tractable with respect to graph treedepth.The proof uses a well-structured ILP whose coefficients and dual-graph treedepth are bounded by a function of the input treedepth.
  • Treedepth results: Set of Degrees MST is W[1]-hard parameterized by treedepth plus feedback vertex number, even on unweighted graphs with |D(v)| ≤2.A gadget encoding vector-summing choices supports a reduction from a W[1]-hard Multidimensional Subset Sum variant.
  • Other structural parameters: Set of Degrees MST is fixed-parameter tractable by vertex cover on unweighted graphs, whereas Specified Degree MST is W[1]-hard after deleting vertices to pathwidth ≤4 and treewidth ≤3.The vertex-cover algorithm reduces the problem to generalized B-matching.

2 Preliminaries

The preliminaries define degree-constrained spanning-tree variants and the structural parameters used to classify them. They also establish basic graph and set notation.

  • Notation: The notation degG(v), NG(v), induced subgraphs, bipartite subgraphs, and integer-set operations is fixed for subsequent arguments.The paper also defines N0, interval notation, multiplicities, and set subtraction.
  • Problem definitions: Set of Degrees MST seeks a minimum-weight spanning tree with degT(v) ∈ D(v) for every vertex.For Bounded Degree MST the requirement is degT(v) ≤ D(v), while Specified Degree MST requires degT(v) = D(v).
  • Graph parameters: The treedepth of a graph is the minimum depth of a rooted elimination tree in which every graph edge joins an ancestor and a descendant.The elimination tree has the graph vertices as its nodes.
  • Graph parameters: The vertex cover number is the minimum size of a vertex cover, while feedback vertex number is the minimum number of vertices whose deletion leaves a forest.These parameters measure different vertex-deletion restrictions.

3 FPT by Treedepth

The treedepth algorithm assigns edge choices to elimination-tree vertices and uses connectivity partitions, rank constraints, and an ILP to enforce spanning-forest structure and degree requirements.

  • 3.1 Setup for the Algorithm: The algorithm starts from a given rooted elimination tree R of height k and assigns every graph edge to its deeper endpoint.Each vertex chooses one subset of its owned edges for inclusion in the selected subgraph.
  • 3.1 Setup for the Algorithm: For each elimination-tree vertex v, Gv contains selected edges at or below v, including edges that can reach ancestors of v.The ILP tracks how the selected subgraph connects the ancestors A+_v.
  • 3.3 ILP correctness: The ILP combines projection, cut, and rank constraints so each selected Gv is a spanning forest and the root instance is a spanning tree.Additional constraints encode vertex degrees and minimize the selected tree's weight.
  • 3.1 Setup for the Algorithm: Connectivity partitions record which ancestors belong to the same connected component of the selected subgraph.A partition is realized by a forest whose component vertex sets equal its blocks.
  • 3.2 Connectivity Partitions: Partition rank equals the number of edges in a realizing forest, and exceeding that rank with the same component structure implies a cycle.The rank is bounded by the number of edges in the underlying graph or multigraph.
  • 3.2 Connectivity Partitions: Partition joins combine connectivity information by taking the components formed by the union of realizing forests.The join is associative, and refinement implies nondecreasing rank.

3.2 ILP Formulation

The ILP selects local edge sets and connectivity partitions, then combines choice, projection, cut, rank, degree, and objective constraints to encode a spanning tree.

  • 3.2 ILP Formulation: The formulation introduces integer variables s_v,S indicating which admissible local edge set S is selected at each vertex.Each variable is binary, with 0 ≤ s_v,S ≤ 1.
  • 3.2 ILP Formulation: Connectivity-partition variables record how the selected forests connect the ancestor sets A_v^+ and A_v^- for each vertex.The partitions summarize connectivity information needed by the inductive formulation.
  • Choice Constraints: Choice constraints select local edge sets and the associated connectivity partitions for every vertex.These constraints determine the selected edges and partition states used throughout the formulation.
  • Projection Constraints: Projection constraints enforce consistency between selected connectivity partitions on related ancestor sets.They use restriction of a partition with respect to a subset.
  • 3.2 ILP Formulation: Cut and rank constraints establish that each selected subgraph is a spanning forest and induces its chosen connectivity partition.The inductive lemma also ensures that every component intersects the relevant ancestor set.
  • 3.2 ILP Formulation: The root-level connectivity condition implies that the entire selected subgraph is a spanning tree.The formulation then adds degree constraints and an objective measuring the selected tree's weight.

Cut Constraints

The cut-constraint construction combines child connectivity information with local edges and forces each selected partition to refine the resulting join.

  • Cut Constraints: For each vertex, the relevant connectivity information is the partition induced on its ancestor set A_v^+ by the selected forest in G_v.Edges outside G_v do not affect connectivity among the vertices of D_v^- above v.
  • Cut Constraints: Selecting a local edge set S and child partitions produces a join representing connectivity in the union of the local and child subgraphs.For a leaf, the join contains only the partition induced by the local edge set.
  • Cut Constraints: Cut constraints force the selected partition Π to be finer than the join of the local and child connectivity partitions.This condition is imposed for every block and every nonempty proper subset of that block.
  • Cut Constraints: The partition lemma certifies refinement by requiring some joined partition to touch both sides of every nontrivial cut within each block.The proof derives a contradiction if a block of the target partition is not contained in a join block.

Rank Constraints

Rank constraints complement the cut constraints by forcing equality of connectivity partitions and certifying acyclicity of the recursively assembled subgraphs.

  • Rank Constraints: Rank constraints force the rank of the selected partition to equal both the join rank and the sum of the component partition ranks.Together with the cut inequalities, this establishes equality between the selected partition and the join.
  • Rank Constraints: A finer partition with the same rank as another partition must equal it.The proof uses the fact that equal ranks imply equal numbers of blocks, then establishes a bijection between the blocks.
  • Rank Constraints: The union of edge-disjoint forests is acyclic exactly when the sum of their partition ranks equals the rank of their joined connectivity partition.The argument reduces the condition to a multigraph on the common boundary vertex set.
  • Rank Constraints: For each component forest, the construction contracts its boundary connectivity into a tree before forming the edge-disjoint union of these boundary multigraphs.The resulting edge count is the sum of the component connectivity ranks.

Degree Constraints

The degree-constraint construction represents admissible incident-edge selections locally and uses them to encode vertex degree requirements in the spanning-tree ILP.

  • Degree Constraints: For every vertex u, the formulation selects an edge set S_u from its admissible family S_u.The global selected edge set is the union of these local selections.
  • Degree Constraints: The selected edges incident with a vertex determine the local degree constraint C_v^deg.The construction introduces this constraint for every vertex.

Objective

Because the sets O(v) partition E(G), the objective counts each selected edge's weight exactly once.

  • The objective sums the weights of selected edges over the edge-partition sets O(v), counting each edge exactly once.

3.3 Proof of Correctness

The correctness proof establishes a correspondence between feasible ILP solutions and degree-respecting spanning trees with equal objective value, then uses this encoding to obtain an FPT algorithm parameterized by treedepth.

  • 3.3 Proof of Correctness: A feasible ILP assignment selects local forests and connectivity structures used to construct a spanning tree.
  • 3.3 Proof of Correctness: The constructed spanning tree has weight equal to the ILP objective because the edge sets O(v) partition E(G).
  • 3.3 Proof of Correctness: Each constructed tree respects the degree requirements because the ILP degree constraints equal the tree degrees at every vertex.
  • 3.3 Proof of Correctness: Conversely, every degree-respecting spanning tree yields a feasible ILP assignment with the same objective value.
  • 3.3 Proof of Correctness: The ILP can be normalized and solved in FPT time using bounded domains, treedepth, and bounded maximum constraint coefficient.

4 W-Hardness for Set of Degrees MST

The reduction proves W[1]-hardness for Set of Degrees MST on unweighted graphs with degree sets of size at most two, parameterized by treedepth plus feedback vertex number.

  • 4 W-Hardness for Set of Degrees MST: The reduction starts from strongly W[1]-hard Simple Multidimensional Partitioned Subset Sum.
  • 4 W-Hardness for Set of Degrees MST: Deleting the root and target vertices leaves a forest with longest path at most nine, giving feedback vertex number at most d + 1 and treedepth at most d + 10.
  • 4 W-Hardness for Set of Degrees MST: Selection and gate gadgets ensure that exactly one vector is chosen from each set P_i.
  • 4 W-Hardness for Set of Degrees MST: Target vertices encode the coordinate-wise sum of the selected vectors through their prescribed degrees.
  • 4 W-Hardness for Set of Degrees MST: The reduction is correct in both directions: a feasible spanning tree yields an SMPSS solution, and an SMPSS solution yields a feasible spanning tree.
  • 4 W-Hardness for Set of Degrees MST: Therefore, Set of Degrees MST is W[1]-hard for treedepth plus feedback vertex number, even on unweighted graphs with |D(v)| ≤2.

5 W-Hardness for Specified Degree MST

The section establishes W[1]-hardness for Specified Degree MST under vertex deletion to graphs of pathwidth at most 4 and treewidth at most 3, even on unweighted graphs. The reduction uses 2-label gadgets that are compiled into ordinary specified-degree instances while preserving solution existence.

  • Reduction framework: A 2-label gadget gives a degree-two vertex four incident edges partitioned into two label pairs, requiring a solution to choose one pair consistently.The replacement graph has only degree-two new vertices and realizes the same two forced routings.
  • Reduction framework: The reduction constructs an intermediate Specified Degree MST instance with 2-label gadgets and compiles each gadget using Lemma 22.Lemma 22 preserves existence of a feasible spanning tree when a 2-label gadget is replaced by the displayed graph.
  • Encoding: The constructed choice gadgets encode selecting one vector from each set while routing all unselected vectors through their associated paths.The selection vertices have degree requirements arranged so one vertex selects a vector and the other accounts for the remaining vectors.
  • Encoding: Lemma 23 proves that selecting a path endpoint forces either all path edges or all corresponding attachment edges, yielding the intended routing behavior.The proof uses the path vertices’ degree requirements and the consistency condition of the 2-label gadgets.
  • Correctness: The reduction is correct in both directions: a consistent feasible spanning tree implies a positive SMPSS instance, and every positive SMPSS instance yields such a tree.The reverse construction adds selected-vector edges, unselected paths, and all root edges, then verifies degrees, connectivity, and acyclicity.
  • Complexity consequence: Specified Degree MST is W[1]-hard under vertex deletion to graphs of pathwidth at most 4 and treewidth at most 3, even on unweighted graphs.The reduced graph outside the deletion set has treewidth at most 3, using width-2 decompositions for the replacement components.

6 FPT by Vertex Cover Number

The section gives an FPT algorithm for unweighted Set of Degrees MST parameterized by vertex cover number. It groups non-cover vertices by neighborhood and degree type, guesses the few non-leaf vertices, and reduces the remaining completion problem to generalized B-matching.

  • Main result: Set of Degrees MST is fixed-parameter tractable with respect to vertex cover number on unweighted graphs.The algorithm runs in time f(k)nO(1), where k is the vertex cover number.
  • Type compression: After computing a vertex cover X, non-cover vertices are grouped into types with identical neighborhoods in X and identical degree sets.The number of types is at most 2^(2k+1).
  • Completion step: For each guessed partial tree, the completion is reduced to generalized B-matching with singleton requirements on the non-cover side.The reduction preserves feasible extensions exactly, by matching residual degrees at cover vertices and degree-one requirements elsewhere.
  • Enumeration: The algorithm guesses a multiset of at most k−1 types whose vertices may have degree at least two and enumerates compatible spanning trees on the cover together with these vertices.All remaining non-cover vertices must have degree one in any spanning tree extending the guessed partial tree.
  • Running time: The running time is f(k)nO(1), since the number of type multisets and partial trees depends only on k and each completion test is FPT in k.The generalized B-matching subroutine is applied after polynomial-time construction of each instance.
  • Correctness: The algorithm is correct because it accepts exactly when some guessed partial tree has a feasible generalized B-matching completion.Lemma 32 proves both directions of this equivalence.

7 Concluding Remarks

The concluding remarks identify an unresolved weighted vertex-cover case for Set of Degrees MST and give a bounded-admissible-degree extension. They also relate the similar behavior of Specified and Bounded Degree MST to a structure-preserving reduction.

  • Open limitation: The weighted Set of Degrees MST case parameterized by vertex cover number remains open.The authors identify FPT generalized B-matching on weighted bipartite graphs as the key missing ingredient.
  • Additional tractability: Set of Degrees MST is fixed-parameter tractable for vertex cover number plus the maximum number of admissible degrees per vertex.The proof sketch branches on cover-vertex degrees and introduces choice variables for non-cover admissible degrees.
  • Relationship between variants: A reduction from Bounded Degree MST to Specified Degree MST preserves almost all of the original graph structure, explaining their similar parameterized behavior.The reduction adds pendant vertices, one auxiliary vertex, and a connecting edge while transforming degree requirements.
Loading 2608.25530v1…