Abstrakt. I parameteriserad komplexitet varje problem instans 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 inmatning instans till en instans med storlek polynomial i k. Många problem har visat sig erkänna polynomiska kärnor, men det är först nyligen som ett ramverk för att visa icke-existens av polynomiska kärnor har utvecklats av Bodlaender et al. [4] och Fortnow och Santhanam [9]. I detta papper 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: -Vi visar att Steiner Tree problem parameteriseras av antalet terminaler och lösning storlek k, och Connected Vertex Cover och kapaciated Vertex Cover problem inte erkänna en polynomial kärna. De två senare resultaten är förvånande eftersom det närbesläktade Vertex Cover problemet medger en kärna av storlek 2k. -Alon och Gutner få en k poly(h) kärna för Dominating Set i HMinor Free Graphs parameteriserade av h =  och lösning storlek k och fråga om kärnor av mindre storlek finns [2]. Vi löser delvis denna fråga genom att visa att Dominating Set i H-Minor Free Graphs inte tillåter en kärna med storlek polynom i k + h. -Harnik och Naor få en "kompression algoritm" för Sparse Subset Sum problem [13]. Vi visar att deras algoritm är i huvudsak optimal eftersom fallen inte kan komprimeras ytterligare. -Hitting Set och Set Cover tillåter en kärna av storlek k O(d) när parameteriserad av lösningsstorlek k och maximal uppsättning storlek d. Vi visar att ingen av dem, tillsammans med den unika täckning och Bounded Rank delade uppsättningar problem, medger en polynom kärna. Alla resultat är under antagande att polynomhierarkin inte kollapsar till den tredje nivån. Förekomsten av polynomkärnor för flera av de problem som nämns ovan var öppna problem som uttryckligen anges i litteraturen [2, 3, 11, 12, 14]. Många av våra resultat utesluter också förekomsten av komprimeringsalgoritmer, ett begrepp som liknar kärnorisering definieras av Harnik och Naor [13], för problemen i fråga.
Varken STEINER TREE eller STEINER FOREST medger en polynomkärna på allmänna grafer REF, såvida inte polynomhierarkin kollapsar.
Incompressibility through Colors and IDs
{'venue': 'IN PROCEEDINGS OF ICALP 2009, VOLUME 5555 OF LNCS', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}