
-
生物通官微
陪你抓住生命科技
跳动的脉搏
无长爪稀疏图中的最大权独立集
《ACM Transactions on Algorithms》:Max Weight Independent Set in sparse graphs with no long claws
【字体: 大 中 小 】 时间:2026年09月26日 来源:ACM Transactions on Algorithms 1.4
编辑推荐:
摘要AI摘要摘要摘要对于图 G 和 H,如果 G 不包含 H 作为诱导子图,则称 G 是 H-自由的。早在20世纪80年代初,Alekseev就观察到,除非 H 的每个连通分量都是路径或细分爪形图(即通过对三叶星形的每条边进行若干次细分(可能为零次)而得到的图),否则最大权独
本摘要由自动化工具生成,未经本文作者撰写或审阅。它旨在支持发现过程,帮助读者评估相关性,并帮助相邻研究领域的读者理解该工作。它旨在补充作者提供的摘要,后者仍然是论文的主要摘要。全文仍是权威记录版本。点击此处了解更多信息。
点击此处对此摘要的准确性、清晰度和实用性进行评论。这样做将有助于改进和未来的重新生成版本。
AI生成的摘要
由自动系统基于已发表的文章文本生成。
版本创建于2026年9月17日。
本文研究了通过排除诱导子图来定义的图类中的最大权独立集问题。已知对于大多数禁止图,该问题在计算上仍然是困难的。主要未解决的情况涉及其连通分量为路径或细分爪形图的森林,包括由多个不相交的细分爪形图组成的图。先前的研究仅为选定的小规模情况建立了多项式算法,而更一般的图类已知具有准多项式或亚指数算法。本文研究了使这些情况变得可行的额外稀疏性和结构性限制。
第一个主要结果涉及最大度有界的图。对于固定的正整数d和t,作者提供了一种算法,该算法要么找到一个由d个不相交的细分爪形图(三条臂长度均为t)组成的诱导子图,要么计算最大权独立集。当度上界和禁止子图参数固定时,其运行时间是顶点数的多项式。因此,最大权独立集可以在有界度图中,排除相关路径和细分爪形图族中任意固定图的情况下,在多项式时间内求解。
第二个结果用稀疏性条件取代了有界度假设。对于固定的d、t和s,作者为排除d个不相交的细分爪形图作为诱导子图、并排除每部分有s个顶点的完全二部图作为子图的图提供了多项式时间算法。此类双团排除涵盖了广泛的稀疏图类。该结果也适用于同时排除细分爪形图、固定团和固定平衡双团的图。
这些算法依赖于结构性分解和递归动态规划。扩展条带分解推广了线图的结构,将图划分为粒子。如果已知这些粒子的独立集解,则可以通过辅助匹配计算将它们组合起来。一个关键分解定理要么检测出禁止构型,要么产生一个小区隔集和一个其粒子最多包含相关顶点一半的条带分解。为了避免在分隔集邻域上进行准多项式分支,作者引入了问题的边界版本,该版本记录在有限端点集上所有可能的独立集选择。
对于稀疏图,证明还利用不存在大型顶点块来获得具有有界粘合度和每个体躯中仅有有限个高度顶点的树分解。算法在这些异常顶点上进行分支,并递归处理由此产生的分量和条带粒子。论文得出结论,无限制的polynomial可解性仍然是开放问题,但确定了在问题可多项式时间求解的重要结构性条件,并为排除细分爪形图和固定团的图提出了更广泛的猜想。
本文开发了用于研究扩展条带分解所表示的图类中最大权独立集的结构和算法工具。其论证有两个主要组成部分。第一部分证明充分高连通的图必然包含若干受控构型之一。第二部分解释了如何通过辅助图扩展条带分解所关联的匹配来编码图中的独立集。这些结果共同支持基于分解的算法,并阐明了如何将局部优化问题组合成全局解。
结构部分使用Ramsey理论论证和连通性。一个块是一个顶点集,其成员在删除少于规定数量的顶点后仍然相互连通。根据Menger定理,此类块中的每对顶点之间存在许多内部不相交路径。在保留块的顶点的大型子集后,这些路径可以选择不经过其他保留顶点。根据连接路径是否很长对顶点对进行分类。如果存在许多远距离对,则对初始路径段应用Ramsey论证可得一个大的完全二部子图或一个诱导细分星形。如果远距离对有限,则可以组装许多短路径为一个有界长度的大团的细分。一个单独的结果然后将此细分转化为完全二部子图或大完全二部图的适当诱导细分。后者包含被禁止的细分三叶星形集合。因此,排除相关完全二部图和诱导星形构型的图具有有界块。这证明了主定理所需的结构性引理,并表明强连通性必然导致少数障碍之一。
算法部分研究了一种扩展条带分解,其粒子根据宿主图边、宿主顶点和三角形对顶点进行划分或组织。某些粒子对被声明为冲突的。独立族不包含冲突的粒子,其成员不相交且互不相邻。原图的每个独立集通过记录每条条带的哪些端点包含所选顶点以及哪些粒子未被使用来诱导这样的族。反之,粒子的选择与辅助图中的匹配一一对应。该匹配记录了宿主顶点是否选择了相邻条带,以及两端是否选择了同一条带。这种对应关系允许通过普通匹配算法以多项式时间处理局部选择之间的兼容性约束。