Unlabelled Partition Systems: Optimization and Complexity
Paolo M. Camerini, Francesco Maffioli · SIAM Journal on Algebraic and Discrete Methods · 1984
In this paper we consider unlabelled partition systems, i.e. independence systems $(S,\mathcal{B})$, where the ground set S—of m elements— is partitioned into n blocks and for each base $B \in \mathcal{B}$ the number of blocks containing i elements of B is exactly $c_i $— a given nonnegative integer—for each $i = 0,1, \cdots ,m$. For any weighting $w:S \to \mathbb{Z}$, we show that the problem asking for a most weighted base is solvable in polynomial time. When $c_{k - 1} + c_k = n$ for some k, $0 < k\leqq m$, we have a matroid, called unlabelled partition matroid. We also introduce a matroid operation, called star, which preserves linear representability. Finally, we investigate the computational complexity of optimum intersection and parity problems for structures of this kind. These arise naturally in many degree-constrained subgraph problems, when only the number of vertices with prescribed degree is assigned, disregarding the vertices identities.