I parameteriserad komplexitet, varje problem exempel kommer med en parameter k, och ett parameteriserat problem sägs erkänna en polynom kärna om det finns polynom tid preprocessing regler som minskar inmatningen instans till ett exempel med storlek polynomial i k. Många problem har visat sig erkänna polynomiala kärnor, men det är först nyligen som ett ramverk för att visa icke-existens av polynomiska kärnor för specifika problem har utvecklats av Fortnow och Santhanam [2008]. Med få undantag har alla kända kärnoriseringsresultat erhållits genom att direkt tillämpa detta ramverk. I den här artikeln, visar vi hur man kombinerar dessa resultat med kombinatoriska minskningar som använder färger och ID för att bevisa kärnor lägre gränser för en mängd grundläggande problem. För att följa med ger vi en sammanfattning av våra huvudsakliga resultat. Alla resultat är under antagande att polynomhierarkin inte kollapsar till den tredje nivån. -Vi visar att problemet STEINER TREE parameteriseras av antalet terminaler och lösning storlek k, och den CONNECTED VERTEX COVER och KAPACITERADE VERTEX COVER problem inte erkänna en polynom kärna. De två senare resultaten är överraskande eftersom det närbesläktade VERTEX COVER-problemet medger en kärna med högst 2k hörn. med h =  och lösningsstorlek k, och fråga om det finns kärnor av mindre storlek. Vi löser delvis denna fråga genom att visa att DOMINERING I H-MINOR FRI GRAPHS inte tillåter en kärna med storlek polynom i k + h. -Harnik och Naor [2007] få en "kompressionsalgoritm" för SPARSE SUBSET SUM problem. Vi visar att deras algoritm i huvudsak är optimal genom att visa att fallen inte kan komprimeras ytterligare. -HITTING SET och SET COVER problem är bland de mest studerade problem i algoritmik. Båda problemen medger en kärna av storlek k O(d) när den parameteriseras av lösningsstorlek k och maximal inställd storlek d. Vi visar att ingen av dem, tillsammans med UNIQUE COVERAGE och BUNDEN RANK DISJOINT SETS problem, medger en polynom kärna. Förekomsten av polynomkärnor för flera av de problem som nämndes tidigare var ett öppet problem som uttryckligen angavs i litteraturen [Alon och Gutner 2008; Betzler 2006; Moser et al. År 2007............................................................................................................. Många av våra resultat utesluter också förekomsten av komprimeringsalgoritmer, ett begrepp som liknar kärnorisering definierad av Harnik och Naor [2007], för problemen i fråga.
Om problemet med oviktade Steinerträd parametriseras av lösningsstorleken, är det känt att det inte finns någon polynomkärna (exakt) om inte coNP-NP/Poly.
Kernelization Lower Bounds Through Colors and IDs
{'venue': 'TALG', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}