I detta dokument överväger vi problemet med att testa om ett diagram har avgränsat arboricitet. Den familj av grafer med avgränsad arboricity inkluderar, bland annat, avgränsade grad grafer, alla mindre slutna graf klasser (t.ex. plana grafer, grafer med avgränsad trädbredd) och slumpmässigt genererade preferentiella bifogade grafer. Grafer med avgränsad arboricitet har studerats i stor utsträckning tidigare, särskilt eftersom de för många problem möjliggör mycket effektivare algoritmer och/eller bättre approximationsförhållanden. Vi presenterar en tolerant testare i sparse-graf modellen. Den sparse-grafer modell ger tillgång till grad frågor och grannar frågor, och avståndet definieras med avseende på det faktiska antalet kanter. Mer specifikt skiljer vår algoritm mellan grafer som är nära att ha arboricity α och grafer som c ·  på långt avstånd från att ha arboricity 3α, där c är en absolut liten konstant. Förfrågan komplexitet och körtid för algoritmen är där n betecknar antalet hörn och m betecknar antalet kanter. När det gäller beroendet av n och m är detta bundet optimalt upp till polylogaritmiska faktorer, eftersom det krävs frågor (n/ m) (och α = O ( ε m)). Vi lämnar det som en öppen fråga om beroendet av 1/ på kan förbättras från kvasi-polynom till polynom. Våra tekniker inkluderar en effektiv lokal simulering för att approximera resultatet av en global (nästan) skogsnedbrytningsalgoritm samt en skräddarsydd procedur för kantprovtagning.
Eden m.fl. REF studerade tolerant testning av avgränsad arboricitet i den allmänna grafmodellen och visade nästan snäva gränser när det gäller beroendet av n och m.
Testing bounded arboricity
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}