Skip to main content
Presentation
The Set Splittablity Problem
Idaho Conference on Undergraduate Research
  • Peter Bernstein
  • Cashous Bortner, University of Nebraska - Lincoln
  • Shuni Li, Macalester College
  • Connor Simpson, Cornell University
  • Samuel Coskey, (Mentor), Boise State University
Abstract

A collection of sets is called splittable if there is a set S such that for each set B in the collection, the intersection of S and B is half the size of B. Splittability is a generalization of graph colorability, which is an active area of research with numerous applications such as scheduling and matching. We show that the problem of deciding whether a collection is splittable is NP-complete. Nevertheless we characterize splittability for some special collections. Finally we study a further generalization called p-splittability, in which the splitter S is required to contain a given fraction of each set B.

Comments

Poster #W10

Citation Information
Peter Bernstein, Cashous Bortner, Shuni Li, Connor Simpson, et al.. "The Set Splittablity Problem"
Available at: http://works.bepress.com/samuel_coskey/15/