On the complexity of sign-nonsingularity and equal unions of sets

ABSTRACT

A family of nonempty sets has the equal union property (EUP) if and only if there exist two nonempty disjoint subfamilies having the same union. If, in addition, every set in the family is used, we have the full equal union property (FEUP). A family with more sets than points always has the equal union property. On the other hand, if there are more points than sets, recognizing both the EUP and FEUP is NP-complete. A recent striking and difficult result by Robertson, Seymour, Thomas, and independently, McCuaig, implies that for square families (the same number of sets as points) recognition of the EUP is polynomial-time. In contrast to this, we give a simple argument below to show that FEUP is NP-complete in the square case.

REFERENCES

• 1: E. J. Cockayne, R. M. Dawes and S. T. Hedetniemi, Total domination in graphs, Networks 10 (1980) 211--219.
• 2: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 3: B. Green, D. Olesky, and P. van den Driessche, Classes of sign nonsingular matrices with a specified number of zero elements, Linear Algebra and Its Applications 248 (1996) 253--275.
• 4: David P. Jacobs , Robert E. Jamison, A note on equal unions in families of sets, Discrete Mathematics, v.241 n.1-3, p.387-393, October 28, 2001 [doi>10.1016/S0012-365X(01)00124-8]
• 5: D. P. Jacobs and R. E. Jamison, Complexity of Recognizing Equal Unions in Families of Sets, submitted.
• 6: V. Klee, R. Ladner, and R. Manber, Signsolvability revisited, Linear Algebra and Its Applications, 59 (1984), 131--157.
• 7: B. Lindström, A theorem on families of sets, J. of Combinatorial Theory (A) 13 (1972), 274--277.
• 8: T. J. Lundy, J. Maybee, and J. Van Buskirk, On maximal sign-nonsingular matrices, Linear Algebra and Its Applications, 247 (1996), 55--81.
• 9: J. Maybee and J. Quirk, Qualitative problems in matrix theory, SIAM Review 11 (1969), 30--51.
• 10: W. McCuaig, Pólya's permanent problem, manuscript (93 pages), June, 1997, submitted to Electronic J. of Comb.
• 11: William McCuaig , Neil Robertson , P. D. Seymour , Robin Thomas, Permanents, Pfaffian orientations, and even directed circuits (extended abstract), Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.402-405, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258625]
• 12: N. Robertson, P. D. Seymour, and R. Thomas, Permanents, Pfaffian orientations, and even directed circuits, Annals of Math. (to appear).
• 13: C. Thomassen, Sign-nonsingular matrices and even cycles in directed graphs, Linear Algebra and Its Applications, 75 (1986), 27--41.
• 14: H. Tverberg, On equal unions of sets, in Studies in Pure Mathematics, edited by L. Mirsky, Academic Press, London, 1971, 249--250.