Fine-Grained Complexity of Computing
Degree-Constrained Spanning Trees

The techniques used to obtain the above results – or any other known results on computing constrained spanning trees (see, e.g., [47]) – do not seem to translate into our setting. In fact, as our first contribution (Theorem 5.1) we rule out an algorithm with single exponential running time with constant dependence on the parameter, in contrast to the treewidth-based bounds discussed above. More precisely, we establish an SETH-based lower bound that essentially excludes any algorithm solving Specified Degree MST (the easiest of the three problems considered here) in time faster than ${𝒪}^{\ast }({(2r)}^{\mathrm{pw}(G)})$, where $r$ is the maximum degree requirement in the image of $D$, even if $G$ is edge-unweighted. We complement this lower bound with a tight algorithmic upper bound that holds for the most general of the three kinds of degree constraints and for polynomially bounded weight functions. In particular, we obtain a randomized algorithm solving Set of Degrees MST in time ${𝒪}^{\ast }({(2r)}^{\mathrm{pw}(G)})$ (Theorem 4.1) and show that this algorithm can also be translated to treewidth, albeit with an “almost optimal” running time of ${𝒪}^{\ast }({(2r+2)}^{\mathrm{tw}(G)})$ (Theorem 4.3).

The above results raise the question of whether one can also solve these problems on more general inputs, notably unweighted dense graphs.²²2Weights in simple dense graphs such as cliques can be used to model instances on arbitrary graphs. More concretely, can we efficiently compute degree-constrained spanning trees by exploiting the classical graph parameter clique-width ($\mathrm{cw}$)? As our next contribution, in Theorem 3.1 we obtain a highly non-trivial deterministic $n^{𝒪(\mathrm{cw})}$-time algorithm solving Set of Degrees MST on unweighted $n$-vertex graphs³³3As is common in related fine-grained upper bounds, we assume that a corresponding decomposition is provided as a witness [19, 1]. – a result which is tight under the ETH [20] and generalizes the known algorithm for Hamiltonian Path under the same parameterization [1].

Under current complexity assumptions, neither Theorem 4.1 nor Theorem 3.1 can be improved to yield fixed-parameter algorithms for our problems of interest under the considered structural parameterizations – indeed, any such algorithm would necessarily violate the aforementioned lower bounds for instances with sufficiently large $r$. However, the question still remains whether one can obtain (tight) fixed-parameter algorithms under different, more restrictive parameterizations. As our third and final set of contributions, we obtain tight “fixed-parameter” running time bounds with respect to the graph parameter cutwidth $\mathrm{ctw}$ [10, 44]. In particular, we design a randomized algorithm solving Set of Degrees MST in time ${𝒪}^{\ast }(3^{\mathrm{ctw}(G)})$ (Theorem 4.2) and a complementary SETH-based lower bound which excludes running times of the form, e.g., ${𝒪}^{\ast }({2.999}^{\mathrm{ctw}(G)})$, even for Specified Degree MST in the edge-unweighted case (Theorem 5.2).

We summarize all these results in Table 1. We remark that all our upper bounds work for the most general variant, namely Set of Degrees MST, while all our lower bounds are obtained for the most restrictive variant, Specified Degree MST, implying that, surprisingly, all three problems have the same complexity for each of the considered parameters.

Finally, we show that our technique for the clique-width upper bound can be adapted to obtain an ETH-tight single-exponential XP algorithm for the Exact Leaf Spanning Tree problem parameterized by clique-width. This settles the last remaining fine-grained question arising from the classical work of Cygan et al. [16, 17], as mentioned in the very recent work of Bojikian and Kratsch [7].

We formally define the different variants of the degree-constrained spanning tree problems studied in this work.

Bounded Degree MST and Specified Degree MST are defined analogously, but there the images of $D$ are sets of the form $[i]$ or $\{i\}$ (for some integer $i$), respectively. We use $r$ to denote ${\max }_{v\in V(G),x\in D(v)}x$. For the unweighted versions of the problems above, we omit the edge weights $w$ and the cost bound $B$ from the input and hence instances merely consist of a pair $(G,D)$. The unweighted versions of all three considered problems are $\mathrm{𝖭𝖯}$-hard as they admit a straightforward reduction from Hamiltonian Path. Clearly, (weighted) Set of Degrees MST generalizes both (weighted) Bounded Degree MST and (weighted) Specified Degree MST by definition. There is also a trivial weight- and graph-preserving reduction from (weighted) Specified Degree MST to (weighted) Bounded Degree MST where instances of Specified Degree MST not satisfying ${\sum }_{v\in V(G)}d(v)=2n-2$ can be rejected, while an instance that satisfies this equality can be turned into an equivalent instance of Bounded Degree MST by replacing $D(v)=\{i\}$ for each $v\in V(G)$ with $D(v)=[i]$.

As mentioned earlier, as an additional contribution we also obtain a more efficient algorithm for the Exact Leaf Spanning Tree problem:

To obtain our algorithm for Set of Degrees MST on (unweighted) graphs parameterized by clique-width, our high-level aim is to employ the typical leaf-to-root dynamic programming approach used in almost all applications of structural graph parameters. There, one intuitively seeks to identify and maintain a correspondence between a suitably defined notion of a “partial solution” in the graph constructed so far – the processed graph – and a (typically combinatorial and compact) representation of that partial solution that is stored as an entry in our records. However, attempting to follow this approach directly for any of our variants over a clique-width decompositions fails, as the number of natural “representations” of partial solutions is not bounded by $n^{f(\mathrm{cw})}$ (for any $f$). In order to circumvent this issue and obtain the sought-after single-exponential $\mathrm{𝖷𝖯}$ algorithm, we will “decompose” these initial representations into collections of more concise representations for partial solutions.

Towards this, we use a two-step representation procedure which characterizes the properties of the processed graph with a set of “nice” footprints that together are compatible with the same set of partial solutions in the rest of the graph. Note that the representation via footprints that we obtain is, by its nature, existential: instead of representing each partial solution Sol in the processed graph by a single footprint (as is standard), we use a set of nice footprints. Crucially, we provide a guarantee that for every full solution extending Sol there exists at least one footprint that can be extended to a (potentially very different) full solution.

Our main contribution is a “requirement shifting” technique, that allows us, in the first place, to build a natural representation of a partial solution, but also more crucially, to reduce each such natural representation into a set of “nice” representations. Concretely, at each step of a clique-decomposition, one builds a partial labeled graph $H$ of the final graph $G$ with the vertices of $H$ partitioned into $k$ label classes. In a hypothetical solution, each vertex of $H$ will still receive a certain number of additional edges that have not been created yet. We call this number the (remaining) requirement of the vertex, whereas the intersection of the hypothetical solution with $H$ forms a spanning forest in that graph.

In a clique-decomposition, all vertices of the same label in $H$ will act as twins (i.e., receive the same added neighbors) in future steps of the decomposition. It is not difficult to show that one can accumulate the requirements of all vertices of the same label in each connected component of a partial solution to a single vertex. To see why this is valid, note that if the current partial solution is to be extended to a full solution in the final graph, then we can reroute the edges attached to vertices of the same label in a connected component to a single vertex representing all these vertices, without changing the degree requirements, the connectivity or the acyclicity of the rest of the graph. We refer to Figure 1(a)-(b) for an illustration of this idea.

Note that a connected component of zero requirement cannot be connected to any other component in the rest of the graph. Therefore, such a component either forms a final solution (if it spans all vertices of the graph), or the considered partial solution cannot be extended to a full solution. Thus, we can assume that there is at most one connected component with requirement zero.

Therefore, a natural representation $R$ of a partial solution $F$ in $H$ can be defined as a multiset of vectors of length $k$, where for each connected component $C$ of $F$ we add a vector to $R$ with the $i$th coordinate of this vector is defined by the total remaining degree requirement of all vertices with label $i$ in that component (see Figure 1(c)). We call this representation a pattern for $F$. Using standard arguments, one can show that this builds a correct representation of the family of partial solutions, and that can be extended correctly along the decomposition, counting the total number of solutions in the graph. This basic representation via patterns forms the foundation for our arguments. However, the total number of such patterns is not bounded by $n^{f(k)}$ for any function $f$, as each coordinate of each vector can take values up to $n$, and a dynamic program directly building on these would need to store multisets of up to $n$ such vectors.

In order to overcome this problem, we introduce a second layer of representation, that serves as the baseline for our technique. The end goal is to reduce each pattern to a compact family of “nice” patterns that we use to index our dynamic programming tables. Formally, we define nice patterns as follows:

In order to achieve this, we show that each pattern $R$ that is not nice can be reduced into two new “nicer” patterns $R_1$, $R_2$ (i.e., each of $R_1$, $R_2$ has strictly fewer non-zero entries in non-unit vectors than $R$). Crucially, $R$ behaves as an “OR” of $R_1$ and $R_2$. We remark that this existence-preserving guarantee differs from the parity-preserving representations typically employed in conjunction with the Cut&Count technique – in fact, our approach yields deterministic algorithms parameterized by clique-width.

In particular, we show on one hand that both $R_1$ and $R_2$ are weaker than $R$ in the sense that each valid extension of either of $R_1$, $R_2$ is also a valid extension for $R$. On the other hand, we also prove that $R_1$ and $R_2$ together are exactly as strong as $R$. In order to build $R_1$ and $R_2$ from $R$, we branch over the ways in which two components of a partial solution are connected to each other in the final graph, which allows to shift (the rest of) the degree requirements between these two components. This allows us to accumulate requirements in fewer “big” components, resulting in nice patterns.

It is not hard to see that the total number of nice patterns is bounded by $n^{𝒪(k)}$ which matches our desired running time. However, since creating a nice pattern requires us to apply the shifting operation exhaustively, a brute-force recursive application of shifting could lead to an exponential blow-up in the number of patterns before they become nice. In order to overcome this problem, we apply the shifting operation in a carefully structured way which guarantees that the size of the intermediate pattern families never exceeds $n^{𝒪(k)}$ – see Figure 2 for an overview.

A second challenge the algorithm needs to overcome is that when one would need to add edges inside $H$, it is not immediately obvious how this changes our patterns. We describe how this challenge can be overcome in the next paragraph which details the algorithm’s operation, but to facilitate the presentation of our ideas we design our dynamic programming algorithm along the closely related notion of NLC-width and NLC-decompositions. This is without loss of generality, as a clique-decomposition can be transformed into an NLC-decomposition of the same width in polynomial time [37]. The advantage of NLC-width here is that it avoids adding edges into the graph processed so far, which is important for dealing with the opaque representations we need to use for the algorithm.

We process the NLC-decomposition in a bottom-up manner, distinguishing two types of nodes: introduce vertex nodes, and join nodes. The latter performs a disjoint union of two previously constructed graphs, adds edges between these two graphs according to a set of specified label pairs, and relabels vertices based on a specified relabeling function.

For an introduce vertex node, the created graph contains a single partial solution, namely the forest consisting of the single introduced vertex. Here, instead of keeping a single entry in our table for this partial solution, at this stage we already account for all possible target requirements of the created vertex and keep a separate entry for each option.

For a join node, on a high level, we start by combining each pair of nice patterns at the two children nodes. For each such pair, our goal is to iterate over all possible ways of selecting the edges between them to include in the solution. This will result in a new family of partial solutions; after that, we apply the corresponding relabeling operations on the resulting family. We will then represent the resulting partial solutions using a family of nice patterns via the process described in Figure 2, thus completing the computation of our records for the node.

The most challenging part of the algorithm is to handle the aforementioned edge selection step. Note that a join operation could add $\mathrm{\Omega }(n^2)$ edges between a pair of partial solutions, meaning that a direct approach would iterate over an exponential number of new partial solutions. To overcome this challenge, we first observe that adding an edge between two “unit-requirements” creates a connected component of zero-requirement, therefore we restrict to choosing at most one such edge. Using this, we can show that the exponentially-many ways of adding edges collapse into $n^{𝒪(k)}$ possible resulting patterns.

In particular, we distinguish three types of edges: the (at most one) edge between two unit components, edges between two big components, and edges between a big component and a unit component. The algorithm first exhaustively branches over the first two types of edge. Second, we branch to determine the number of edges of the third type incident to each vertex of a big component, and the number of unit components of each label incident to these “type-3” edges. Note that each type-3 edge “consumes” the requirement of this unit component, whereas the exact choice of which unit components are connected to which big components does not affect the resulting representation. Therefore, for each such choice, it suffices to verify the validity of the choice. We show that this final verification can be done via a reduction to the well-known Bipartite $b$-Matching problem, which is solvable in polynomial time [13]. This allows us to establish our first main result:

Before we proceed with the remaining results for degree-constrained MST problems, we show that the shifting technique developed for Theorem 3.1 can also be adapted to obtain an ETH-tight algorithm for the Exact Leaf Spanning Tree problem parameterized by clique-width. Again, a partial solution of this problem is a spanning forest, where we mainly care about the number of leaves of each label in a connected component of the forest, and whether at least one inner vertex of each label exists in that component. Therefore, a natural definition of a pattern representing a partial solution consists of a vector that counts the number of isolated vertices of each label, and a multiset that contains an element for each remaining component. Each such element is a pair consisting of a vector counting the number of leaves of each label, and a set of labels that contain the labels of the inner vertices in that component.

In contrast to the previous section, instead of shifting requirements, intuitively we shift leaves (and inner vertices) between connected components of a partial solution. This requires us to allow, among others, the construction of connected components consisting of a single inner vertex. We achieve this by adding an additional “virtual” label $0$, that will allow us to build artificial leaves and inner vertices when needed, whose count will not be considered in the final solution. After that we can apply a similar shifting technique as before, where we guess which leaves or inner vertices connect two components in the final solution, and shift all the other leaves and inner vertices between them accordingly.

The same notion of compatibility and equivalence of partial solutions as used for Set of Degrees MST carries over to this setting as well. The main difficulty arises when we attempt to resolve the bottleneck of adding edges between two partial solutions. In particular, the previous solution via using $b$-matching will not apply to this setting – indeed, it is possible to create an exponential number of valid non-collapsing representations by adding different sets of join edges to a pair of partial solutions. This means that iterating over all possible representations instead of sets of edges will still not suffice to achieve our targeted running time bound. Intuitively, this issue arises because for Exact Leaf Spanning Tree, the result of adding an edge between a unit component and a big component depends on the label of the isolated vertex, whereas for Set of Degrees MST this was not the case.

We overcome this problem by introducing a more fine-grained notion of equivalence, where we require two equivalent partial solutions to not only complete the same set of partial solutions in the rest of the graph (as was the case for Set of Degrees MST), but additionally that the number of added edges between each pair of labels is the same. We note that, while this notion of equivalence is stronger than the one defined previously, the shifting operation employed there would also preserve this stronger notion of equivalence. Crucially, with this stronger notion of equivalence we can avoid iterating over all subsets of edges, and can instead add the edges one by one and reduce the resulting partial solutions after adding each edge. While more technically involved, this approach avoids the aforementioned exponential blow-up and yields an algorithm with the desired running time.