On the Min-Max Star Partitioning Number

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}(\mathrm{\mid }E{\mathrm{\mid }}^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 (\mathrm{\Delta })\cdot \mathrm{\mid }E\mathrm{\mid }\cdot \min \{\mathrm{\mid }V{\mathrm{\mid }}^{\frac{2}{3}},\mathrm{\mid }E{\mathrm{\mid }}^{\frac{1}{2}}\})$, where $\mathrm{\Delta }$ is maximum node degree in $G$. In contrast to the unweighted setting, we show that a node-weighted decision variant of this problem is $\mathtt{\text{strongly}}\mathtt{\text{NP-complete}}$ even without capacity constraints. Furthermore, we provide an extensive comparison to the problem of minimizing the minimum indegree satisfying node capacity constraints.