Minimum Spanning Trees with Bounded Degrees of Vertices in a Specified Stable Set
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2022
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909212934668288 |
|---|---|
| author | Brause, Christoph Harant, Jochen Hörsch, Florian Mohr, Samuel |
| author_facet | Brause, Christoph Harant, Jochen Hörsch, Florian Mohr, Samuel |
| contents | Given a graph $G$ and sets $\{α_v~|~v \in V(G)\}$ and $\{β_v~|~v \in V(G)\}$ of non-negative integers, it is known that the decision problem whether $G$ contains a spanning tree $T$ such that $α_v \le d_T (v) \le β_v $ for all $v \in V(G)$ is $NP$-complete. In this article, we relax the problem by demanding that the degree restrictions apply to vertices $v\in U$ only, where $U$ is a stable set of $G$. In this case, the problem becomes tractable.
A. Frank presented a result characterizing the positive instances of that relaxed problem. Using matroid intersection developed by J. Edmonds, we give a new and short proof of Frank's result and show that if $U$ is stable and the edges of $G$ are weighted by arbitrary real numbers, then even a minimum-cost tree $T$ with $α_v \le d_T (v) \le β_v $ for all $v \in U$ can be found in polynomial time if such a tree exists. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2210_04669 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Minimum Spanning Trees with Bounded Degrees of Vertices in a Specified Stable Set Brause, Christoph Harant, Jochen Hörsch, Florian Mohr, Samuel Combinatorics Discrete Mathematics Given a graph $G$ and sets $\{α_v~|~v \in V(G)\}$ and $\{β_v~|~v \in V(G)\}$ of non-negative integers, it is known that the decision problem whether $G$ contains a spanning tree $T$ such that $α_v \le d_T (v) \le β_v $ for all $v \in V(G)$ is $NP$-complete. In this article, we relax the problem by demanding that the degree restrictions apply to vertices $v\in U$ only, where $U$ is a stable set of $G$. In this case, the problem becomes tractable. A. Frank presented a result characterizing the positive instances of that relaxed problem. Using matroid intersection developed by J. Edmonds, we give a new and short proof of Frank's result and show that if $U$ is stable and the edges of $G$ are weighted by arbitrary real numbers, then even a minimum-cost tree $T$ with $α_v \le d_T (v) \le β_v $ for all $v \in U$ can be found in polynomial time if such a tree exists. |
| title | Minimum Spanning Trees with Bounded Degrees of Vertices in a Specified Stable Set |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2210.04669 |