Fine-Grained Complexity of Computing Degree-Constrained Spanning Trees
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911643529641984 |
|---|---|
| author | Bojikian, Narek Firbas, Alexander Ganian, Robert Hoang, Hung P. Szilágyi, Krisztina |
| author_facet | Bojikian, Narek Firbas, Alexander Ganian, Robert Hoang, Hung P. Szilágyi, Krisztina |
| contents | 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 each vertex to a list of admissible degrees, an upper bound on the degrees, 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 graph parameters of the input graph $G$. In particular, we present SETH-tight upper and lower bounds for these problems when parameterized by the pathwidth and cutwidth, an ETH-tight algorithm parameterized by the cliquewidth, 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_15226 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Fine-Grained Complexity of Computing Degree-Constrained Spanning Trees Bojikian, Narek Firbas, Alexander Ganian, Robert Hoang, Hung P. Szilágyi, Krisztina Data Structures and Algorithms 68Q27 F.2 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 each vertex to a list of admissible degrees, an upper bound on the degrees, 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 graph parameters of the input graph $G$. In particular, we present SETH-tight upper and lower bounds for these problems when parameterized by the pathwidth and cutwidth, an ETH-tight algorithm parameterized by the cliquewidth, 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. |
| title | Fine-Grained Complexity of Computing Degree-Constrained Spanning Trees |
| topic | Data Structures and Algorithms 68Q27 F.2 |
| url | https://arxiv.org/abs/2503.15226 |