En graf H är en kvadratrot av en graf G om G kan erhållas från H genom tillägg av kanter mellan två hörn i H som är av avstånd 2 från varandra. Square Root problemet är att avgöra om en given graf medger en kvadratrot. Vi anser att detta problem för planar diagram i samband med "avståndet från trivialitet" ram. För ett heltal k är en planar+kv graf en graf som kan göras planar genom avlägsnande av som mest k hörn. Vi bevisar att en generalisering av kvadratroten, där vissa kanter är föreskrivna att vara antingen i eller ur någon lösning, har en kärna av storlek O(k) för planar+kv grafer, när parameteriserade av k. Vårt resultat är baserat på en ny edge reduktion regel som, som vi också ska visa, har en bredare tillämplighet för Square Root problemet. År 1967 kännetecknade Mukhopadhyay [22] de grafer som har en kvadratrot. I linje med den tidigare nämnda NP-fullständighet resultatet av Motwani och Sudan, som dök upp 1994, denna karakterisering leder inte till en polynom-tid algoritm för Square Root. Senare resultat fokuserade på följande två igenkänningsfrågor (G betecknar någon fast graf klass): Hur svårt är det att känna igen kvadrater av grafer av G? Hur svårt är det att känna igen grafer av G som har en kvadratrot? Observera att den andra frågan motsvarar problemet med kvadratrot begränsad till grafer i G, medan den första frågan är densamma som att fråga om en viss graf har en kvadratrot i G. Ross och Harary [24] karakteriserade kvadrater av ett träd och visade att om en ansluten graf har en trädkvadratrot, då denna rot är unik upp till isomorfism. Lin och Skiena [18] gav en linjär tidsalgoritm för att känna igen kvadrater av träd; de visade också att Square Root kan lösas i linjär tid för plana grafer. Le och Tuy [16] generaliserade ovanstående resultat för träd [18, 24] för att blockera grafer. Nestoridis och Thilikos [23] visade att Square Root inte bara är polynom-tid som kan lösas för klassen planara grafer utan för alla icke-triviala mindre slutna grafklasser, dvs. för alla grafklasser som inte innehåller alla grafer och som är stängda under borttagning av vertex, kantradioner och kantkontraktioner. Lau [12] gav en polynom-tid algoritm för att känna igen kvadrater av bipartit grafer; Observera att Square Root är trivial för bipartit grafer, och även för K 4 - fria grafer, eller motsvarande, grafer av klique tal som mest 3, som kvadratrötter av K 4 - fria grafer måste ha maximal grad på högst 2. Milanic, Oversberg och Schaudt [19] visade att linjegrafer bara kan ha bipartitgrafer som kvadratrot. Samma författare gav också en linjär tid algoritm för Square Root begränsad till linjer grafer. Lau och Corneil [13] gav en polynom-tidsalgoritm för att känna igen kvadrater med korrekta intervallgrafer och visade att problemen med att känna igen kvadrater av ackordsgrafer och kvadrater av delade grafer är både NP-komplett. Samma författare visade också att Square Root är NP-komplett även för ackordsgrafer. Le och Tuy [17] gav en quadratictime-algoritm för att känna igen kvadrater av starkt ackordssplitta grafer. Le, Oversberg och Schaudt [14] gav polynomalgoritmer för att känna igen kvadrater av ptolemaic grafer och 3-sun-fri split grafer. I en nyare tidning [15], samma författare förlängde det senare resultatet genom att ge polynom-tid resultat för att känna igen kvadrater av ett antal andra underklasser av split grafer. Milanic och Schaudt [20] visade att Square Root kan lösas i linjär tid för trivialt perfekta grafer och tröskelgrafer. De utgjorde komplexiteten i Square Root begränsad till att dela grafer och cographs som öppna problem. Nyligen bevisade vi att Square Root är linjär-tid lösbar för 3-degenererade grafer och för (K r, P t )-fria grafer för två positiva heltal r och t [8]. Adamaszek och Adamaszek [1] visade att om en graf har en kvadratrot av omkrets minst 6, då denna kvadratrot är unik upp till isomorfism. Farzad, Lau, Le och Tuy [7] visade att känna igen grafer med en kvadratrot av omkrets minst g kan lösas med polynomtid om g ≥ 6 och NP-komplett om g = 4. Det saknade fallet g = 5 visades vara NP-komplett av Farzad och Karimi [6]. I ett tidigare papper [2] visade vi att Square Root är polynom-tid solvable för grafer av maximal grad 6. Vi ansåg också kvadratrötter inom ramen för parameteriserad komplexitet [3, 2]. Vi bevisade att följande två problem är fastparameterdragbara med parameter k: testa om en ansluten n-vertex-graf med m-kanter har en kvadratrot med högst n − 1 + k-kanter och testa om en sådan graf har en kvadratrot med minst m − k-kanter. I synnerhet, det första resultatet innebär att problemet med att känna igen kvadrater av träd + k grafer, det vill säga grafer som kan ändras till träd genom att ta bort på de flesta k kanter, är fast-parameter dragbar när parameterized av k.
Som visat sig i REF, nedbrytningen av kvadratroten i en graf G genom dess snitt-vertices leder till en specifik typ av träd sönderdelningar för G som kallas "H-tree sönderdelningar".
A Linear Kernel for Finding Square Roots of Almost Planar Graphs
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}