Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2511.22912 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914173692149760 |
|---|---|
| author | Kokai, Toranosuke Suzuki, Akira Suzuki, Takahiro Tamura, Yuma Zhou, Xiao |
| author_facet | Kokai, Toranosuke Suzuki, Akira Suzuki, Takahiro Tamura, Yuma Zhou, Xiao |
| contents | In the context of algorithm theory, various studies have been conducted on spanning trees with desirable properties. In this paper, we consider the \textsc{Minimum Cover Spanning Tree} problem (MCST for short). Given a graph $G$ and a positive integer $k$, the problem determines whether $G$ has a spanning tree with a vertex cover of size at most $k$. We reveal the equivalence between \mcst\ and the \textsc{Dominating Set} problem when $G$ is of diameter at most~$2$ or $P_5$-free. This provides the intractability for these graphs and the tractability for several subclasses of $P_5$-free graphs. We also show that \mcst\ is NP-complete for bipartite planar graphs of maximum degree~$4$ and unit disk graphs. These hardness results resolve open questions posed in prior research. Finally, we present an FPT algorithm for {\mcst} parameterized by clique-width and a linear-time algorithm for interval graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_22912 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Spanning Trees with a Small Vertex Cover: the Complexity on Specific Graph Classes Kokai, Toranosuke Suzuki, Akira Suzuki, Takahiro Tamura, Yuma Zhou, Xiao Data Structures and Algorithms 05C85 In the context of algorithm theory, various studies have been conducted on spanning trees with desirable properties. In this paper, we consider the \textsc{Minimum Cover Spanning Tree} problem (MCST for short). Given a graph $G$ and a positive integer $k$, the problem determines whether $G$ has a spanning tree with a vertex cover of size at most $k$. We reveal the equivalence between \mcst\ and the \textsc{Dominating Set} problem when $G$ is of diameter at most~$2$ or $P_5$-free. This provides the intractability for these graphs and the tractability for several subclasses of $P_5$-free graphs. We also show that \mcst\ is NP-complete for bipartite planar graphs of maximum degree~$4$ and unit disk graphs. These hardness results resolve open questions posed in prior research. Finally, we present an FPT algorithm for {\mcst} parameterized by clique-width and a linear-time algorithm for interval graphs. |
| title | Spanning Trees with a Small Vertex Cover: the Complexity on Specific Graph Classes |
| topic | Data Structures and Algorithms 05C85 |
| url | https://arxiv.org/abs/2511.22912 |