A polynomial-time partitioning algorithm for weighted cactus graphs
share
Partitioning problems where the goal is to partition a graph into connected components are known to be NP-hard for some graph classes but polynomial-time solvable for others. We consider different variants of the (l,u)-partition problem: the p-(l,u)-partition problem and the minimum resp. maximum (l,u)-partition problem. That is partitioning a graph into exactly p or a minimal resp. maximal number of clusters such that every cluster fulfills the following weight condition: the weight of each cluster should to be at least l and at most u. These kind of partitioning problems are NP-hard for series-parallel graphs but can be solved in polynomial time on trees. In this paper we present partitioning algorithms for cactus graphs to show that these partition problems are polynomial-time solvable for this graph class as well.
READ FULL TEXT