2026-09-08T02:22:00Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26427 2026-09-05T19:43:00Z ddc:004 open_access

Fine-Grained Complexity of Computing Degree-Constrained Spanning Trees Bojikian, Narek Firbas, Alexander Ganian, Robert Hoang, Hung P. Szilágyi, Krisztina Parameterized complexity Structural parameters Clique-width fine-grained complexity Spanning tree We investigate the computation of minimum-cost spanning trees satisfying prescribed vertex degree constraints: Given a graph G and a constraint function D, we ask for a (minimum-cost) spanning tree T such that for each vertex v, T achieves a degree specified by D(v). Specifically, we consider three kinds of constraint functions ordered by their generality - D may either assign to each vertex a list of admissible degrees, an upper bound on the degree, or a specific degree. Using a combination of novel techniques and state-of-the-art machinery, we obtain an almost-complete overview of the fine-grained complexity of these problems taking into account the most classical structural graph parameters of the input graph G. In particular, we present SETH-tight upper and lower bounds for these problems when parameterized by pathwidth and cutwidth, an ETH-tight algorithm parameterized by clique-width, and a nearly SETH-tight algorithm parameterized by treewidth. In order to obtain our upper bound for clique-width, we develop a novel technique of double representation through "requirement shifting". Using this technique, we also obtain an ETH-tight single-exponential XP algorithm for the Exact Leaf Spanning Tree problem parameterized by clique-width, which settles the final remaining open case for clique-width from the classical Cut and Count of Cygan et al. [FOCS 2011, TALG 2022]. This shows the versatility of our technique and its potential applicability to other problems as well. Additionally, in order to establish our lower and upper bounds we introduce a number of tools which may be of independent interest, including lazy coloring and "asymptotic" SETH-based reductions for structural parameters. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Narek Bojikian and Alexander Firbas and Robert Ganian and Hung P. Hoang and Krisztina Szilágyi 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.38 urn:nbn:de:0030-drops-264272 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.38 eng https://creativecommons.org/licenses/by/4.0/legalcode