Abstract- Existensen av en polynom kärna för Odd Cycle Transversal var ett ökänt öppet problem i parameteriserad komplexitet. Nyligen löstes detta av de nuvarande författarna (Kratsch och Wahlström, SODA 2012), med en randomiserad polynomkärna för problemet, med hjälp av matroidteori för att koda flödesfrågor över en uppsättning terminaler i storlek polynomial i antalet terminaler (snarare än den totala grafstorleken, som kan vara superpolynomiskt större). I det nuvarande arbetet etablerar vi vidare nyttan av matroidteori för kärnorisering genom att visa tillämpningar av ett resultat på representativa uppsättningar på grund av Lovász (Combinatorial Surveys 1977) och Marx (TCS 2009). Vi visar hur representativa uppsättningar kan användas för att ge en polynomkärna för det svårfångade Nästan 2-sats problemet (där uppgiften är att ta bort som mest k klausuler för att göra en 2-CNF formel satisfiable), lösa ett stort öppet problem i kärnorisering. Vi tillämpar också de representativa sätten verktyg på problemet med att hitta irrelevanta hörn i graf skär problem, det vill säga hörn som kan göras odelbara utan att påverka problemets status. Detta ger de första betydande framstegen mot en polynomkärna för multiway cut-problemet; i synnerhet får vi en polynomkärna för multiway cut-fall med ett begränsat antal terminaler. Båda dessa kärnresultat har betydande spin-off-effekter och producerar de första polynomkärnorna för en rad relaterade problem. Mer allmänt, de irrelevanta vertex resultaten har implikationer för att täcka min-cuts i grafer. I synnerhet, med tanke på en riktad graf och en uppsättning av terminaler, kan vi hitta en uppsättning storlek polynomial i antalet terminaler (en cut-covering set) som innehåller en minsta vertex skär för varje val av källor och sänkor från terminaluppsättningen. På samma sätt, med tanke på en oriktad graf och en uppsättning av terminaler, kan vi hitta en uppsättning hörn, av storlek polynomial i antalet terminaler, som innehåller en minsta multiway cut för varje partition av terminalerna i ett begränsat antal uppsättningar. Båda resultaten är polynom tid. Vi förväntar oss att detta kommer att ha ytterligare applikationer; i synnerhet, vi får direkta, reduktion regelbaserade kärnor för alla problem ovan, i motsats till den indirekta komprimeringsbaserade kärnan som tidigare gavs för Odd Cycle Transversal. Alla våra resultat är randomiserade, med fel sannolikheter som kan göras exponentiellt liten i storleken på indata, på grund av att det behövs en representation av en matris för att tillämpa de representativa uppsättningar verktyg.
Nyligen gavs en polynomkärna för EDGE och NODE MULTIWAY CUT för ett konstant antal terminaler eller avtagbara terminaler REF; dock är frågan om en polynomkärna i det allmänna fallet fortfarande öppen.
Representative Sets and Irrelevant Vertices: New Tools for Kernelization
{'venue': '2012 IEEE 53rd Annual Symposium on Foundations of Computer Science', 'journal': '2012 IEEE 53rd Annual Symposium on Foundations of Computer Science', 'mag_field_of_study': ['Mathematics', 'Computer Science']}