距离矩阵被随机篡改后，最小生成树仍可近似：一般篡改下达到对数因子，且无需查询真实距离

在距离可被任意增减的一般篡改模型下，仅凭被篡改的距离就能算出期望代价不超过真实最小生成树对数倍的生成树，这回答了此前悬而未决的开放问题。 此前该模型只有下界：即使允许自适应选点并查询真实距离，也无法做到优于对数因子的近似，而算法侧没有任何非平凡上界。 该近似因子与既有信息论下界一致，说明在只观察被篡改距离的前提下已无法再改进；同一结果还确认了原模型提出者的猜想。

做法是先在被篡改距离上找一棵“几乎支配”的生成树，再取其路径捷径作为输出。 支配树要求任意两点在树上的距离不超过它们被观察到的直接距离；任意增减会破坏这一性质，于是放宽为：任意足够大的点集内只有很小比例的点对违反该性质。 分析依赖一个高概率事件：任意足够大的点集内部被篡改的边只占很小比例，从而保证存在只用未篡改边、代价接近最优的几乎支配树。

三种篡改方向对应不同的近似能力：只增时多项式时间即可达到常数因子，只减时只能到对数因子，任意增减时同样是对数因子。 只减情形下，直接取被篡改距离上的最小生成树可能严重偏离，因为对手可把跨簇距离压低而诱导出错误结构。 只减情形另有一个拟多项式时间算法达到更小的对数多项式因子，并有证据表明多项式时间达到该因子不太可能；只增情形则输出被篡改距离上的最小生成树即可。

结论适用于每条点对距离以固定常数概率被独立篡改、且算法只能读取被篡改距离的度量空间；除拟多项式时间算法外，算法是确定性的，期望只对随机篡改集合取。一般增减模型下尚无已知的高效算法，这被明确留作开放问题。

只减情形下，多项式时间达到对数多项式因子被认为不太可能，依据是区分可着色图与特定 quietly planted 分布的困难性，这属于证据而非定理。一般篡改模型的高效算法仍未知，且当篡改概率较大时不存在对数因子近似。