Icke-adaptiv grupptestning innebär att godtyckliga undergrupper av n-objekt grupperas i olika pooler. Därefter testas varje pool och defekta föremål identifieras. En grundläggande fråga är att minimera antalet pooler som krävs för att identifiera högst d defekta objekt. Motiverad av tillämpningar i nätverkstomografi, sensornätverk och infektionsutbredning formuleras en variation av grupptestproblem på grafer. Till skillnad från konventionella grupptestproblem måste varje grupp här uppfylla de begränsningar som följer av en graf. Till exempel, objekt kan associeras med hörn och varje pool är någon uppsättning noder som måste vara sökväg ansluten. I detta papper är ett test förknippat med en slumpmässig promenad. I detta sammanhang motsvarar konventionell grupptestning det särskilda fallet med en fullständig graf på n hörn. För intressanta klasser av grafer erhålls ett ganska överraskande resultat, nämligen att antalet tester som krävs för att identifiera d defekta objekt i stort sett liknar vad som krävs i konventionella grupptestproblem, där inga sådana begränsningar för sammanslagningar införs. Om T (n) motsvarar blandningstiden för grafen G, visas det att med m = O(d 2 T 2 (n) log (n/d)) icke-adaptiv provning kan man identifiera de defekta objekten. För Erdős-Rényi slumpmässiga graf G(n, p) och expandergrafer med konstant spektralgap är det följaktligen tillräckligt att m = O(d 2 log 3 n) icke-adaptiva tester för att identifiera d defekta objekt. Därefter anses ett specifikt scenario uppstå i nätverkstomografi, för vilket det visas att m = O(d 3 log 3 n) icke-adaptiva tester är tillräckliga för att identifiera d defekta objekt. Bullermotsvarigheter till grafen som begränsar grupptestningsproblem beaktas, för vilka parallella resultat utvecklas. Vi diskuterar också kortfattat förlängningar till kompressiv avkänning på grafer.
Kompressiv avkänning i nätverkstomografi diskuteras först i REF.
Graph-Constrained Group Testing
{'venue': 'IEEE Transactions on Information Theory', 'journal': 'IEEE Transactions on Information Theory', 'mag_field_of_study': ['Mathematics', 'Computer Science']}