Detta arbete studerar hårdheten av att hitta oberoende uppsättningar i hypergrafer som är antingen 2-färgbara eller är nästan 2-färgs, dvs.. kan vara 2-färgad efter att ha tagit bort en liten bråkdel av hörn och händelsen hyperkanter. För att vara exakt, säg att en hypergraf är (1 - ε) - nästan 2- färgbara om ta bort en ε bråkdel av dess hörn och alla hyperkanter incident på dem gör den återstående hypergraf 2- färgbar. I synnerhet bevisar vi följande resultat. • För en godtyckligt liten konstant γ > 0, det finns en konstant  på > 0, sådan att, med tanke på en 4-uniform hypergraph på n hörn som är (1 - ε)-nästan 2-färgade för ε = 2  på, det är kvasi-NPhard 1 att hitta en oberoende uppsättning av n 2 hörn. • För eventuella konstanter ε, δ > 0, ges som inmatning en 3-uniform hypergraph på n hörn som är (1 - ε) - nästan 2-färgade, är det NP-hård att hitta en oberoende uppsättning av δn hörn. • Förutsatt att d-to-1 Games Antag följande håller. För varje konstant δ > 0, givet en 2-färgad 3-uniform hypergraf på n hörn, är det NP-hård att hitta en oberoende uppsättning av δn hörn. Hårdheten resultatet på oberoende uppsättning i nästan 2-färgade 3-uniform hypergraphs var tidigare känd endast om man antar Unique Games Conjecture. I detta arbete bevisar vi resultatet villkorslöst, genom att kombinera Fourier analysteknik med Multi-Layered PCP av [DGKR03]. För oberoende uppsättningar i 2-färgade 3-uniforma hypergaphs visar vi det första starka hårdhetsresultatet, även om vi antar D-to-1 Games Conjecture. Vår reduktion använder d-to-1 Game som utgångspunkt för att konstruera en Multi-Layered PCP med släthet egenskap. Vi använder analytiska tekniker baserade på Invariance Principe of Mossel [Mos10]. Jämnhetsfastigheten utnyttjas på ett sätt som liknar Håstads [Hås12] och Wenners [Wen12]. Vårt resultat på nästan 2-färgade 4-uniform hypergrafer ger den första nästan polynom hårdhetsfaktor för oberoende uppsättning i hypergrafer som (nästan) färg med ständigt många färger. Den överbryggar delvis gapet mellan den tidigare bästa nedre gränsen av poly (log n) och den algoritmiska övre gränserna för n.(1). Detta uppvisar också en flaskhals för att förbättra algoritmiska tekniker för hypergraph färgning.
Såvitt vi vet är vårt arbete det första att tillämpa variansbaserade tekniker för att bevisa NP-hårdhet av Hypergraph Coloring / Vertex Cover problem (Khot och Saket REF använde dem för att bevisa hårdhet att hitta en oberoende uppsättning i 2-färgbara 3-uniform hypergraphs, förutsatt att d-to-1 gissningen).
Hardness of Finding Independent Sets in 2-Colorable and Almost 2-Colorable Hypergraphs
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}