Vi är glada att tillägna denna undersökning om kärnan i Vertex Cover-problemet, till professor Juraj Hromkovič med anledning av hans 60-årsdag. Vertex Cover-problemet kallas ofta för Drosophila för parameteriserad komplexitet. Den har en lång historia. Nya och värdiga perspektiv kommer alltid att visas först med konkreta resultat här. Denna undersökning diskuterar flera forskningsriktningar i Vertex Cover-kärnan. Barriärgraden av Vertex Cover diskuteras. Vi har reduceringsregler som kärnor hörn av liten grad, inklusive i detta papper nya resultat som minskar grafer nästan till minimum grad fem. Kan denna process fortsätta för evigt? Vad är den minsta vertex-grader barriären för polynom-tid kärnisering? Om man antar Exponential-Time Hypotesen, finns det en minimigrad barriär. Idén om automatiserad kärnorisering diskuteras. Vi rapporterar här de första experimentella resultaten av en AI-styrd förgreningsalgoritm för Vertex Cover vars logik verkar vara möjlig att tillämpa för att hitta reduktionsregler för att kärna små-graders hörn. Undersökningen belyser ett centralt öppet problem i parameteriserad komplexitet. Lycklig
För mer information om vertex-omslagets historik, se Fellows et al. Hoppa över det.
What is known about Vertex Cover Kernelization?
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}