Weisfeiler-Leman维数的计算复杂性

《ACM Transactions on Computational Logic》：Computational complexity of the Weisfeiler-Leman dimension

Weisfeiler-Leman维度的计算复杂度研究，证明在4色类约束下判断维度≤k为NP难，但对5色类及固定k≥2提出多项式算法，并证明其AC0最优性。

　　

摘要AI 摘要

要查看此由 AI 生成的摘要，您必须具有高级访问权限。

了解更多登录

摘要

摘要

图的自卫费勒-莱曼维数（Weisfeiler-Leman dimension）是指最小的正整数 $k$，使得自卫费勒-莱曼算法能够将图 $G$ 与其他所有非同构图区分开来。换句话说，这个维数也是最小的正整数，使得图 $G$ 可以用包含 $(k\; +\; 1)$ 个变量的逻辑（包含计数功能）来描述。这个维数是衡量图描述性或结构复杂性的一个标准指标，最近在机器学习领域得到了广泛应用。本文研究了计算自卫费勒-莱曼维数的复杂性。我们发现，即使图 $G$ 被限制在只有 $4$ 个颜色的情况下，判断其自卫费勒-莱曼维数是否最多为 $k$ 也是一个 NP 难问题。因此，我们研究了该问题的参数化版本。对于每个固定的正整数 $k$ ≥ 2，我们提供了一个多项式时间算法，用于判断给定图的自卫费勒-莱曼维数是否最多为 $k$。此外，我们还证明了在这些颜色类的限制下，这个算法是最优的，因为该问题在对数空间一致（logspace-uniform）的 AC₀ 归约下属于 P 难问题。对于更大的颜色类限制以及每个固定的正整数 $k$ ≥ 2，我们还为交换结构（即每个颜色类都存在交换自同构群的结构）提供了一个多项式时间决策算法。

虽然我们考虑的图类可能看起来相当有限，但具有 $4$ 个交换颜色的图包括了 CFI 图和多路图（multipedes），这些图构成了几乎所有已知关于自卫费勒-莱曼算法的难题实例和下界的基础。

AI 摘要

AI 生成的摘要（实验性)

此摘要是由自动化工具生成的，并非由文章作者撰写或审核。它旨在帮助读者发现研究内容的相关性，并协助来自相关研究领域的读者理解本文的工作。它是对作者提供的摘要的补充，作者提供的摘要仍是本文的官方总结。完整文章才是权威版本。点击此处了解更多。

点击 此处 对摘要的准确性、清晰度和实用性进行评论。您的反馈将有助于改进未来的摘要版本。

要查看此由 AI 生成的通俗语言摘要，您必须具有高级访问权限。