Jump to content

Set splitting problem

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by C. lorenz (talk | contribs) at 15:24, 15 April 2014 (Cleaned up references.). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

In computational complexity theory, the Set Splitting problem is the following decision problem: given a family F of subsets of a finite set S, decide whether there exists a partition of S into two subsets S1, S2 such that all elements of F are split by this partition, i.e., none of the elements of F is completely in S1 or S2. Set Splitting is one of Garey&Johnson's classical NP-complete problems.[1]

Variants

The optimization version of this problem is called Max Set Splitting and requires finding the partition which maximizes the number of split elements of F. It is an APX-complete[2] (and hence NPO-hard) problem. When each element of F is restricted to be of cardinality exactly k, the decision variant is called Ek-Set Splitting and the optimization version Max Ek-Set Splitting. For k ≥ 2, the former remains NP complete and the latter APX complete.[3] The Weighted Set Splitting is a variant in which the subsets in F have weights and the objective is to maximize the total weight of the split subsets.

Connection to Other Problems

Set Splitting is special case of the Not-All-Equal Satisfiability problem without negated variables. Additionally, Ek-Set Splitting equals non-monochromatic coloring of k-uniform hypergraphs. For k=2, the optimization variant reduces to the well-known Maximum cut.[4]

Approximability

For k ≥ 4, Ek-Set Splitting is approximation resistant. That is, unless P=NP, there is no polynomial-time (factor) approximation algorithm which does essentially better than a random partition.[5][4]

Fixed-Parameter Tractability

An alternative formulation of the decision variant is the following: given an integer k, does there exist a partition of S which splits at least k subsets of F? This formulation is fixed-parameter tractable - for every fixed k, there exists a polynomial-time algorithm for solving the problem.[6]

References

  1. ^ Garey, M.R. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W.H. Freeman. ISBN 0-7167-1045-5. {{cite book}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)
  2. ^ Petrank, Erez (1994). "The Hardness of Approximation: Gap Location". Computational Complexity. Springer.
  3. ^ Lovász, László (1973). Coverings and Colorings of Hypergraphs. Symposium on Theory of Computing. ACM.
  4. ^ a b Guruswami, Venkatesan (2003). "Inapproximability Results for Set Splitting and Satisfiability Problems with no Mixed Clauses". Algorithmica. Springer.
  5. ^ Håstad, Johan (2001). "Some Optimal Inapproximability Results". Journal of the ACM. ACM.
  6. ^ Dehne, Frank; Fellows, Frances; Rosamond (2003). An FPT Algorithm for Set Splitting. Graph Theoretic Concepts in Computer Science. Springer.