On the Min-Max Star Partitioning Number
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910565370167296 |
|---|---|
| author | Feldmann, Sarah Schürenberg, Torben |
| author_facet | Feldmann, Sarah Schürenberg, Torben |
| contents | In this paper, we introduce a novel star partitioning problem for simple connected graphs $G=(V,E)$. The goal is to find a partition of the edges into stars that minimizes the maximum number of stars a node is contained in while simultaneously satisfying node-specific capacities. We design and analyze an efficient polynomial time algorithm with a runtime of $\mathcal{O}(|E|^2)$ that determines an optimal partition. Moreover, we explicitly provide a closed form of an optimal value for some graph classes. We generalize our algorithm to find even an optimal star partition of linear hypergraphs, multigraphs, and graphs with self-loop. We use flow techniques to design an algorithm for the star partitioning problem with an improved runtime of $\mathcal{O}(\log(Δ) \cdot |E| \cdot \min\{|V|^{\frac{2}{3}},|E|^{\frac{1}{2}}\})$, where $Δ$ is maximum node degree in $G$. In contrast to the unweighted setting, we show that a node-weighted decision variant of this problem is \texttt{strongly NP-complete} even without capacity constraints. Furthermore, we provide an extensive comparison to the problem of minimizing the minimum indegree satisfying node capacity constraints. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_07370 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On the Min-Max Star Partitioning Number Feldmann, Sarah Schürenberg, Torben Combinatorics F.2.2; G.2.1; G.2.2 In this paper, we introduce a novel star partitioning problem for simple connected graphs $G=(V,E)$. The goal is to find a partition of the edges into stars that minimizes the maximum number of stars a node is contained in while simultaneously satisfying node-specific capacities. We design and analyze an efficient polynomial time algorithm with a runtime of $\mathcal{O}(|E|^2)$ that determines an optimal partition. Moreover, we explicitly provide a closed form of an optimal value for some graph classes. We generalize our algorithm to find even an optimal star partition of linear hypergraphs, multigraphs, and graphs with self-loop. We use flow techniques to design an algorithm for the star partitioning problem with an improved runtime of $\mathcal{O}(\log(Δ) \cdot |E| \cdot \min\{|V|^{\frac{2}{3}},|E|^{\frac{1}{2}}\})$, where $Δ$ is maximum node degree in $G$. In contrast to the unweighted setting, we show that a node-weighted decision variant of this problem is \texttt{strongly NP-complete} even without capacity constraints. Furthermore, we provide an extensive comparison to the problem of minimizing the minimum indegree satisfying node capacity constraints. |
| title | On the Min-Max Star Partitioning Number |
| topic | Combinatorics F.2.2; G.2.1; G.2.2 |
| url | https://arxiv.org/abs/2408.07370 |