《Journal of Computer and System Sciences》:Restricting Infections in the Threshold Model on Graphs by Vertex Immunization
编辑推荐:
考虑图G=(V,E)上的离散时间感染过程:在时间τ=0从初始感染顶点集S?V(G)开始;对τ≥1,顶点v∈V(G)被感染当且仅当其在上一时间步τ?1至少有阈值t(v)个已感染邻居。当没有更多顶点可被感染时过程结束。研究人员研究(k,l)-影响免疫限制((k,l
考虑图G=(V,E)上的离散时间感染过程:在时间τ=0从初始感染顶点集S?V(G)开始;对τ≥1,顶点v∈V(G)被感染当且仅当其在上一时间步τ?1至少有阈值t(v)个已感染邻居。当没有更多顶点可被感染时过程结束。研究人员研究(k,l)-影响免疫限制((k,l)-Influence Immunization Bounding, (k,l)-IIB)的一个变体,其中需要判定是否可通过从G中免疫(移除)l个顶点,使过程结束时G中感染顶点数不超过k≥|S|。多数结果限于k=|S|的情形,称为总限制(Total Restriction)。研究结果表明,即使限制在分裂图(split graph)与二部图(bipartite graph)中,该问题以l为参数仍为W[2]-难(W[2]-hard);即使限制在最大度为三的二部平面图(bipartite planar graph)中仍为NP完全(NP-complete)。研究人员给出总限制情形的多项式时间求解方法:若对任意v∈V(G)?S有t(v)=1,或G为具有任意阈值函数的树(tree)。若G为完全图(complete graph),对任意k≥|S|和任意阈值函数t,研究人员给出多项式时间算法计算将感染限制在至多k个顶点所需的最小免疫顶点集;该结果同时适用于上述变体与原始问题,原始问题仅允许免疫V(G)?S中的顶点。
研究背景方面,图上的感染模型受到经济学、营销学、流行病学和物理学等领域关注;阈值模型(threshold model)以离散时间不可逆过程描述感染扩散:初始感染集S在τ=0开始,τ≥1时未感染顶点v若在上一时间步至少有t(v)个已感染邻居则被感染,已感染顶点保持感染,直到无新顶点可感染。既有研究关注影响最大化(Influence Maximization)和目标集选择(Target Set Selection),也关注遏制感染的Firefighter问题及(k,l)-IIB。原始(k,l)-IIB要求免疫集Y?V(G)?S且|Y|≤l,使最终感染顶点数不超过k。本文研究允许免疫S中顶点的变体,并重点关注k=|S|的总限制(Total Restriction),即最终感染顶点恰为初始S。开展该研究的原因在于:原始问题已有参数化复杂性结果,但允许免疫初始感染顶点的变体及总限制在分裂图、二部图、平面次立方图、树和完全图等图类上的复杂性与精确算法仍需刻画。研究人员通过困难性归约和算法设计,明确了问题边界,并给出若干可多项式或线性时间求解的情形,为感染遏制提供算法基础。
关键技术方法概括(不超过250字):研究人员采用参数化复杂性归约,从集合覆盖(Set Cover)证明总限制以l为参数W[2]-难;采用经典复杂性归约,从受限平面3-SAT(Restricted Planar 3-Sat, r-Planar-3-Sat)证明NP完全。对可解情形,将总限制化为二部图最小顶点覆盖(minimum vertex cover)并用匹配求解;完全图上按阈值分类、前缀和优化,构造k-约简过程并枚举S中免疫数量;树上采用后序遍历算法并归纳证明最优性;结合组合观察及路径阈值2的归纳上界。无样本队列来源。
研究结果如下。3. 困难性结果:3.1 分裂图与二部图:通过从Set Cover归约,构造分裂图,使团全为感染顶点、独立集为未感染顶点、阈值等于度,证明总限制以免疫顶点最大数l为参数W[2]-难;去掉团内边后得到二部图,得到同样的W[2]-难结论。3.2 平面二部次立方图:通过从r-Planar-3-Sat归约,构造变量gadget与子句顶点,证明所得图为次立方(最大度至多三)二部平面图,且总限制NP完全,阈值等于度。4. 在特定图和若干观察中高效计算最小限制集:组合观察表明,最小总限制集中的每个免疫顶点或属于S或邻接S;当阈值等于度时存在最小总限制集Y?S;路径图阈值均为2时,通过S-交替路径分解与归纳得到R(P,k)≤?n/4?。4.1 当对任意v∈V(G)?S有t(v)=1时的总限制:通过删去S内部边、删除非邻接S顶点及未感染顶点间边,将问题化为二部图最小顶点覆盖,从而多项式时间求解。4.2 完全图的k-限制数:通过阈值分类、前缀和与表达式优化,线性时间求总限制;引入仅易感顶点可免疫的(k,l)-IIB(Susceptible-Only (k,l)-IIB),构造k-约简过程并证明最小性,得到O((k?|S|)n
2)算法;一般(k,l)-IIB通过枚举S中免疫i个顶点,得到O(|S|kn
2)算法,并同时处理原始问题。4.3 树的总限制:采用后序遍历算法,维护残余阈值并决定免疫顶点,线性时间输出最小总限制集,并证明其最优性。5. 结论:总结困难性结果与可解情形;对于树中k≠|S|的(k,l)-IIB是否NP完全留作开放问题,并提出路径、仙人掌图、正则图、分裂图子类、格子图、有向图及感染状态可逆变体等研究方向。
讨论部分总结:作者认为路径、仙人掌图、正则图及分裂图子类等值得探索,Firefighter在毛虫图上的贪心算法具有启发意义,格子等正则图结构明确,有向图版本及感染顶点可变为未感染、未感染可变为感染的变体尚未研究。研究结论部分可翻译为:本研究研究了(k,l)-IIB的一个变体,主要关注总限制;在分裂图和二部图中,该问题以l为参数仍为W[2]-难,在平面二部次立方图中仍为NP完全,且这些困难性结果均针对阈值等于度的总限制情形;当所有未感染顶点阈值为1时,总限制可精确求解;完全图或树在任意阈值下可精确且线性时间求解总限制;在完全图上还给出算法,可对任意有效k,l完全求解该变体与原始(k,l)-IIB;对于树中k≠|S|的情形,作者提出其是否NP完全的问题,并指出若干值得探索的图类和问题变体。