Vi studerar fastighetstester i samband med distribuerade datorer, under den klassiska CONGEST-modellen. Det är känt att testa om en graf är triangelfri kan göras i ett konstant antal rundor, där konstanten beror på hur långt inmatningskurvan är från att vara triangelfri. Vi visar att för varje ansluten 4-node graf H, testa om en graf är H-fri kan göras i ett konstant antal rundor också. Konstanten beror också på hur långt inmatningskurvan är från att vara H-fri, och beroendet är identiskt med det i fråga om att testa trianglar. Därför, särskilt, testa om en graf är K 4 - fri, och testa om en graf är C 4 - fri kan göras i ett konstant antal rundor (där K k betecknar k-node clique, och C k betecknar k-node cykeln). Å andra sidan visar vi att det verkar mycket svårare att testa K k-freeness och C k-freeness för k ≥ 5. Speciellt undersöker vi två naturliga typer av generiska algoritmer för att testa H-frihet, som kallas DFS-testare och BFS-testare. Den senare fångar den tidigare kända algoritmen för att testa förekomsten av trianglar, medan den förra fångar vår generiska algoritm för att testa förekomsten av en 4-node graf mönster H. Vi visar att både DFS och BFS testare misslyckas med att testa K k - frihet och C k - frihet i ett konstant antal rundor för k ≥ 5.
I REF en algoritm för att testa om en graf inte innehåller en specifik subgraf (eller någon isomorf kopia av den) av storlek 4.
Distributed Testing of Excluded Subgraphs
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science']}