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. Set Splitting is one of Garey & Johnson's classical NP-complete problems.[1] The problem is sometimes called hypergraph 2-colorability.

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] problem and hence in NPO.

The set k-splitting problem is stated as follows: given S, F, and an integer k, does there exist a partition of S which splits at least k subsets of F? The original formulation is the restricted case with k equal to the cardinality of F. The Set k-Splitting is fixed-parameter tractable, i.e., if k taken to be a fixed parameter, rather than a part of the input, then a polynomial algorithm exists for any fixed k. Dehne, Fellows and Rosamond presented an algorithm that solves it in time for some function f and constant c.[3]

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 for k ≥ 2 the latter remains APX complete.[4] 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][6]

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 graph coloring of k-uniform hypergraphs. For k=2, the optimization variant reduces to the well-known maximum cut.[6]

References

  1. ^ Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W.H. Freeman. ISBN 0-7167-1045-5.
  2. ^ Petrank, Erez (1994). "The Hardness of Approximation: Gap Location". Computational Complexity. 4 (2). Springer: 133–157. doi:10.1007/BF01202286. S2CID 16433553.
  3. ^ Dehne, Frank; Fellows, Michael; Rosamond, Frances (2003). An FPT Algorithm for Set Splitting (PDF). Graph Theoretic Concepts in Computer Science (WG2003), Lecture Notes in Computer Science. Vol. 2880. Springer. pp. 180–191.
  4. ^ Lovász, László (1973). Coverings and Colorings of Hypergraphs. 4th Southeastern Conference on Combinatorics, Graph Theory, and Computing.
  5. ^ Håstad, Johan (2001). "Some Optimal Inapproximability Results". Journal of the ACM. 48 (4). Association for Computing Machinery: 798–859. doi:10.1145/502090.502098. S2CID 5120748.
  6. ^ a b Guruswami, Venkatesan (2003). "Inapproximability Results for Set Splitting and Satisfiability Problems with no Mixed Clauses". Algorithmica. 38 (3). Springer: 451–469. doi:10.1007/s00453-003-1072-z. S2CID 15541433.

Read other articles:

List of destroyers of the Imperial Russian Navy

This article provides insufficient context for those unfamiliar with the subject. Please help improve the article by providing more context for the reader. (April 2020) (Learn how and when to remove this template message) Российский Императорский флотRossiiskiy Imperatorskiy flotNaval jack (top) and ensign of the Russian NavyActive1696 – February 1917CountryRussian EmpireMilitary unit 1877–1917 The format is: Name, launch year, place of construction (if foreign...

 

Театр часів Російсько-української війни

Ця стаття висвітлює поточну подію. Інформація може швидко змінюватися через розвиток подій, початкові відомості можуть виявитися ненадійними. Останні оновлення цієї статті можуть не відображати найсвіжішу інформацію. Театр часів російсько-української війни — вклю...

 

قائمة نواب رئيس الجمهورية (مصر)

جزء من سلسلة حولالسياسة في مصر الدستور الدستور (قائمة) حقوق الإنسان السلطة التنفيذية الرئيس (قائمة) عبد الفتاح السيسي نائب الرئيس (قائمة) شاغر رئيس مجلس الوزراء (قائمة) مصطفى مدبولي السلطة التشريعية مجلس النواب (قائمة) حنفي جبالي مجلس الشيوخ عبد الوهاب عبد الرازق السلطة الق�...

Contour plowing

Farming practice This article includes a list of general references, but it lacks sufficient corresponding inline citations. Please help to improve this article by introducing more precise citations. (September 2009) (Learn how and when to remove this template message) Contour ploughing, Pennsylvania, 1938 Contour bunding, Catalonia, 2007 Contour bunding or contour farming or contour ploughing is the farming practice of plowing and/or planting across a slope following its elevation contour li...

 

Tour d'Espagne 1960

Tour d'Espagne 1960GénéralitésCourse 15e Tour d'EspagneÉtapes 17Date 29 avril - 15 mai 1960Distance 3 566 kilomètresPays traversé(s) EspagneLieu de départ MadridLieu d'arrivée BilbaoCoureurs au départ 80Coureurs à l'arrivée 24Vitesse moyenne 34,575 km/hRésultatsVainqueur Frans De MulderDeuxième Armand DesmetTroisième Miguel Pacheco FontClassement par points Arthur DecabooterMeilleur grimpeur Antonio KarmanyMeilleure équipe Groene LeeuwTour d'Espagne 1959Tour d'Es...

 

Stasiun Kamioka

Stasiun Kamioka上岡駅Stasiun Kamioka pada 2009LokasiJepangKoordinat32°57′23″N 131°51′44″E / 32.95639°N 131.86222°E / 32.95639; 131.86222Koordinat: 32°57′23″N 131°51′44″E / 32.95639°N 131.86222°E / 32.95639; 131.86222Operator JR KyushuJalur■ Jalur Utama NippōLetak202.4 km dari KokuraJumlah peron1 peron pulauKonstruksiJenis strukturAtas tanahInformasi lainStatusTanpa stafSitus webSitus web resmiSejarahDibuka20 Novembe...

International Intellectual Property Alliance

International Intellectual Property AllianceAbbreviationIIPAFormation1984 (1984)TypePrivate sector coalitionFieldsCopyrightAffiliationsAssociation of American PublishersBusiness Software AllianceEntertainment Software AssociationIndependent Film & Television AllianceMotion Picture AssociationNational Music Publishers' AssociationRecording Industry Association of AmericaWebsiteiipa.org The International Intellectual Property Alliance (IIPA) is a coalition of seven trade associations r...

 

Matt Lauer

Matt LauerLauer di 2012 Time 100LahirMatthew Todd Lauer30 Desember 1957 (umur 66)New York City, New York, ASKebangsaanAmerikaPendidikanUniversitas OhioPekerjaanJurnalis televisiTahun aktif1979–sekarangTempat kerjaNBCUniversal, ComcastGaji$28,000,000 annually[1]TelevisiPembawa acara Today(1997–sekarang)Penyiar berita Today(1994–1997)Suami/istriNancy Alspaugh ​ ​(m. 1981; c. 1988)​ Annette Roque ​(m. 199...

 

Deabeas Owusu-Sekyere

Deabeas Owusu-Sekyere Nazionalità  Paesi Bassi Altezza 184 cm Calcio Ruolo Attaccante Squadra  Zhejiang Zhiye CarrieraGiovanili 200?-2010 SV Amstelland Utd2010-2011 AFC2011-2016 Ajax2016-2017 Twente2017-2020 LeixõesSquadre di club1 2018-2019→  Freamunde28 (4)2020-2022 Paide53 (27)2022-2023 Cangzhou Xiongshi45 (12)2024- Zhejiang Zhiye2 (0) 1 I due numeri indicano le presenze e le reti segnate, per le sole partite di campionato.Il simbolo �...

美国众议院

此條目需要补充更多来源。 (2021年7月4日)请协助補充多方面可靠来源以改善这篇条目，无法查证的内容可能會因為异议提出而被移除。致使用者：请搜索一下条目的标题（来源搜索：美国众议院 — 网页、新闻、书籍、学术、图像），以检查网络上是否存在该主题的更多可靠来源（判定指引）。 美國眾議院 United States House of Representatives第118届美国国会众议院徽章 众议院旗...

 

Філософія

Частина серії проФілософіяLeft to right: Plato, Kant, Nietzsche, Buddha, Confucius, AverroesПлатонКантНіцшеБуддаКонфуційАверроес Філософи Епістемологи Естетики Етики Логіки Метафізики Соціально-політичні філософи Традиції Аналітична Арістотелівська Африканська Близькосхідна іранська Буддій�...

 

The International 2023

The International 2023Tournament informationGameDota 2DatesOctober 12–October 29, 2023AdministratorValveTournamentformat(s)Single Round Robin tournament(Group Stage)Double Elimination Bracket (Playoffs)Host(s)United StatesVenue(s)Seattle Convention Center(Playoffs Weekend)Climate Pledge Arena (Finals Weekend)Participants20 teamsPurseUS$3,380,455Final positionsChampionTeam Spirit1st runner-upGaimin Gladiators2nd runner-upLGD Gaming← 20222024 → The International 2023 (co...

Asia Museum of Modern Art

Museum in Wufeng, Taichung, Taiwan Asia Museum of Modern Art亞洲現代美術館Established24 October 2013; 10 years ago (2013-10-24)LocationWufeng, Taichung, TaiwanCoordinates24°02′49.5″N 120°41′17.5″E / 24.047083°N 120.688194°E / 24.047083; 120.688194Typeart museumArchitectTadao AndoWebsiteOfficial website The Asia Museum of Modern Art (traditional Chinese: 亞洲現代美術館; simplified Chinese: 亚洲现代美术馆; pinyin...

 

Twopence (British pre-decimal coin)

Former official unit of currency of Great Britain and other territories This article is about the pre-decimal coins minted in 1797 in copper and 1818-1820 in silver. For the decimal two pence coin, see Two pence (British decimal coin). TwopenceUnited KingdomValue2d sterlingMass56.7 g (2 oz)Diameter41 mm (1.6 in)EdgePlainCompositionCopperYears of minting1797Mint marksSOHO, below and to the right of Britannia.ObverseDesignProfile of George IIIDesignerConrad Heinrich Küchle...

 

October 1978 papal conclave

Election of Pope John Paul II This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: October 1978 papal conclave – news · newspapers · books · scholar · JSTOR (April 2010) (Learn how and when to remove this message) Papal conclaveOctober 1978Dates and location14–16 October 1978Sistine Chapel, Apostolic Palace,Vat...

Going Clear (film)

2015 film by Alex Gibney Going Clear: Scientology and the Prison of BeliefFilm posterDirected byAlex GibneyWritten byAlex GibneyBased onGoing Clearby Lawrence WrightProduced by Alex Gibney Lawrence Wright Kristen Vaurio Starring Lawrence Wright Mark Rathbun Monique Rathbun Mike Rinder Jason Beghe Paul Haggis Sylvia Taylor Sara Goldberg Tony Ortega Kim Masters Narrated byAlex GibneyCinematographySam PainterEdited byAndy GrieveMusic byWill BatesProductioncompanyJigsaw ProductionsDistributed byH...

 

Grand Prix F1 Hungaria 2011

Grand Prix Hungaria 2011 Lomba ke-11 dari 19 dalam Formula Satu musim 2011← Lomba sebelumnyaLomba berikutnya → HungaroringDetail perlombaanTanggal 31 Juli 2011Nama resmi Formula 1 Eni Magyar Nagydíj 2011Lokasi Hungaroring, Mogyoród, HungariaSirkuit Fasilitas balapan permanenPanjang sirkuit 4.381 km (2.722 mi)Jarak tempuh 70 putaran, 306.630 km (190.531 mi)Cuaca Berawan, rintik hujanPosisi polePembalap Sebastian Vettel Red Bull Racing-RenaultWaktu 1:19.815Putaran terc...

 

1980 USAC Championship Car season

Sports season 1980 USAC Championship Car seasonChampionship Racing LeagueChampion: Johnny RutherfordSeasonRaces5Start dateApril 13End dateJuly 13AwardsNational champion Johnny RutherfordIndianapolis 500 winner Johnny Rutherford← 19791981–82 → The 1980 USAC Championship Car season consisted of five races, beginning in Ontario, California on April 13 and concluding in Lexington, Ohio on July 13. The USAC National Champion and Indianapolis 500 winner was Johnny Rutherford...

Tandoori chicken

Marinated roast chicken dish This article is about the food. For the song, see Tandoori Chicken (song). Tandoori chickenChicken tandoori in Mumbai, IndiaAlternative namesNone[1][2][3][4] [5][6][7][8][9]CourseAppetizer or main courseRegion or stateIndian subcontinent[6][7][8] [10][11][12]Associated cuisineSouth Asian, PunjabiMain ingredientsChicken, dahi (yogurt), honey, tand...

 

Orchies

Orchies L'hôtel de ville. Blason Logo Administration Pays France Région Hauts-de-France Département Nord Arrondissement Douai Intercommunalité Communauté de communes Pévèle-Carembault Maire Mandat Ludovic Rohart 2020-2026 Code postal 59310 Code commune 59449 Démographie Gentilé Orchésiens Populationmunicipale 8 455 hab. (2021 ) Densité 774 hab./km2 Population agglomération 16 770 hab. (2021) Géographie Coordonnées 50° 28′ 32″ nord, 3...