Vi anser att följande naturliga generalisering av binär sökning: i en given oriktad, positivt viktad graf, en vertex är ett mål. Algoritmens uppgift är att identifiera målet genom adaptivt ifrågasätta hörn. Som svar på fråga en nod q, algoritmen lär sig antingen att q är målet, eller ges en kant ut ur q som ligger på en kortaste vägen från q till målet. Vi studerar detta problem i en allmän bullrig modell där varje fråga oberoende får ett korrekt svar med sannolikhet p > 1 2 (en känd konstant), och en (vägledande) felaktig en med sannolikhet 1 − p. Vårt huvudsakliga positiva resultat är att när p = 1 (dvs alla svar är korrekta), log 2 n frågor är alltid tillräckligt. För allmän p, ger vi en (nästan informations-teoretiskt optimal) algoritm som använder, i förväntan, inte mer än (1−δ) log n 1−H(p) +o(log n)+O(log 2 (1/δ)) frågor, och identifierar målet korrekt med sannolikhet minst 1 − δ. Här betecknar H(p) = −(p log p + (1 − p) log(1 − p)) entropin. Den första bundet uppnås av algoritmen som iterativt frågar en 1-median av noderna ännu inte uteslutits; den andra bundet av noggrant upprepade anrop av en multiplikativ vikt algoritm. Även för p = 1, visar vi flera hårdhetsresultat för problemet att avgöra om ett mål kan hittas med K-frågor. Vår övre gräns för log 2 n innebär en kvasipolynom-tid algoritm för oriktade anslutna grafer; vi visar att detta är bäst möjligt under Strong Exponential Time Hypothesis (SETH). Dessutom, för riktade grafer, eller för oriktade grafer med icke-uniforma nod frågekostnader, problemet är PSPACE-fullständig. För en semi-adaptiv version, där man kan fråga r noder var i k rundor, visar vi medlemskap i 2k-1 i polynomhierarkin, och hårdhet för 2k-5.
För allmänna grafer, en strategi som alltid frågar en 1-median (minimering av summan av avstånd över alla hörn) har längd som mest log 2 n REF.
Deterministic and probabilistic binary search in graphs
{'venue': 'STOC 2016', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}