Set splitting problem

Set splitting problem

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. It is an NP-complete problem. [1]

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 NP-hard) problem. The problem remains NP-hard even if all subsets in F contain the same fixed number of elements m greater than 1 [3]

The decision variant of Max Set Splitting, also called "Set Splitting" is stated as follows: given an integer k, whether there exists a partition of S which splits at least k subsets of F? If k taken to be a fixed parameter, then Set Splitting is fixed-parameter tractable, i.e., a polynomial algorithm exists for any fixed k.[3]

The Weighted Set Splitting is a variant in which the subsets in F have weights and the oblective is to maximize the total weight of the split subsets.

References

  1. ^ Garey, M.R.; Johnson, D.S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W.H. Freeman. ISBN 0-7167-1045-5. 
  2. ^ E. Petrank, "The hardness of approximation: Gap location", Computational Complexity, 4(1994), 133–157.
  3. ^ a b "An FPT Algorithm for Set Splitting"

Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • Set splitting — is a logical NP Complete problem which is defined as follows::: Instance : A finite set S and a collection C of finite subsets of S ;:: Query : Can the elements of S be colored with two colors, say red and green, so that no set X ∈ C has all… …   Wikipedia

  • Necklace splitting problem — In mathematics, and in particular combinatorics, the necklace splitting problem arises in a variety of contexts including exact division; its picturesque name is due to mathematicians Noga Alon [1] and Douglas B. West.[2] Suppose a necklace, open …   Wikipedia

  • Splitting field — In abstract algebra, a splitting field of a polynomial with coefficients in a field is a smallest field extension of that field over which the polynomial factors (or splits , hence the name) into linear factors. Contents 1 Definition 2 Facts 3 …   Wikipedia

  • Splitting lemma — In mathematics, and more specifically in homological algebra, the splitting lemma states that in any abelian category, the following statements for short exact sequence are equivalent. Given a short exact sequence with maps q and r: :0 ightarrow… …   Wikipedia

  • Necklace problem — The necklace problem is a problem in recreational mathematics, solved in the early 21st century. Contents 1 Formulation 2 Solution 3 References 4 See also …   Wikipedia

  • Maximum flow problem — An example of a flow network with a maximum flow. The source is s, and the sink t. The numbers denote flow and capacity. In optimization theory, the maximum flow problem is to find a feasible flow through a single source, single sink flow network …   Wikipedia

  • HTTP response splitting — is a form of web application vulnerability, resulting from the failure of the application or its environment to properly sanitize input values. It can be used to perform cross site scripting attacks, cross user defacement, Web cache poisoning,… …   Wikipedia

  • Firing squad synchronization problem — The firing squad synchronization problem is a problem in computer science and cellular automata first proposed by John Myhill in 1957 and published (with a solution) in 1962 by Edward Moore. The problem is analogous to problems of logical design …   Wikipedia

  • Mermaid problem — The Mermaid problem is an observation occasionally mentioned in literature, concerning the difficulty of having sexual intercourse with a mermaid. Although mermaids are commonly depicted as beautiful, variably nude, and enticing, a man attempting …   Wikipedia

  • Hilbert's fifteenth problem — is one of the 23 Hilbert problems set out in a celebrated list compiled in 1900 by David Hilbert. It entails a rigorous foundation of Schubert s enumerative calculus.Splitting the question, as now it would be understood, into Schubert calculus… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”