I detta dokument studerar vi problemet med Target Set Selection som Kempe, Kleinberg och Tardos föreslagit; ett problem som ger en fin ren kombinatorisk formulering för många tillämpningar som uppstår inom ekonomi, sociologi och medicin. Dess ingång är en graf med vertex-trösklar, det sociala nätverket, och målet är att hitta en delmängd av hörn, målet satt, som "aktiverar" ett förspecificerat antal hörn i grafen. Aktivering av en vertex definieras via en så kallad aktiveringsprocess enligt följande: Inledningsvis blir alla hörn i målet aktiva. Därefter vid varje steg i av processen, varje vertex aktiveras om antalet av dess aktiva grannar vid iteration i - 1 överskrider dess tröskel. Aktiveringsprocessen är "monoton" i den meningen att när en vertex är aktiverad, förblir den aktiv för hela processen. Vårt bidrag är följande: Först presenterar vi en algoritm för Target Set Selection som körs i n O(w) tid, för grafer med n hörn och trädbredd begränsas av w. Denna algoritm kan antas till mycket mer allmänna inställningar, inklusive fallet med riktade grafer, viktade kanter, och viktade hörn. Å andra sidan visar vi också att det är högst osannolikt att hitta en n ( ε w) tid algoritm för Target Set Selection, eftersom detta skulle innebära en subexponentiell algoritm för alla problem i SNP. Tillsammans med vårt övre bundna resultat visar detta att den trädbreddsparametern i stor utsträckning avgör komplexiteten i valet av måluppsättning, och bör beaktas vid hanteringen av detta problem i alla scenarier. I den sista delen av tidningen behandlar vi också "non-monotone" varianten av Target Set Selection, och visar att detta problem blir #P-hård på grafer med kantvikter.
I arbetet med REF presenteras en algoritm för val av måluppsättning vars komplexitet bestäms av grafens trädbredd – även om det inte ger några experiment eller bevis för att algoritmen kan skala för stora datauppsättningar.
Treewidth Governs the Complexity of Target Set Selection ∗
{'venue': 'Discret. Optim.', 'journal': 'Discret. Optim.', 'mag_field_of_study': ['Computer Science', 'Mathematics']}