Polynomial recognition of equal unions in hypergraphs with few vertices of large degree (Q2458923): Difference between revisions

A system of nonempty subsets of a finite underlying set has the equal union property if there are two disjoint subfamilies with equal union. If the union covers the entire underlying set, then the system has the full equal union property. The recognition of both properties is NP-complete if the number of points with at least degree three is unbounded. However, as it is shown in this paper, the problems become polynomially solvable if there exists such a constant upper bound.