NeFut Logo NeFut
EN 管理员登录

[算法理论] 复杂性新视角:Flood-It 游戏在 Cograph 扩展中的挑战与突破

发布于:2026-06-24 22:00 最后更新:2026-06-25 10:57
#algorithm #C++ #Graph

Flood-It 是一个单人游戏,目标是在预先着色的图 $G$ 上通过尽可能少的洪水移动使 $G$ 单色化。在每次移动中,选择一个颜色 $c$,并将所有通过单色路径可达的固定支点顶点的顶点重新着色为 $c$。在自由变体中,每次移动可以重新选择支点。决定一个图是否可以在最多 $k$ 次移动中变为单色是 NP-完全的,无论是固定支点还是自由变体。这种复杂性在强结构限制下依然存在,例如在分裂图和树上。自由 Flood-It 变体通常被认为比固定支点变体更困难,因为它在多个图类中仍然保持困难,而后者在某些情况下变得可解,包括共比较图和 AT-自由图。Cographs,即 $P_4$-自由图,是其中少数几个即使对于自由 Flood-It 也能在多项式时间内解决的图类之一,因此我们将其作为起点。

我们考虑 $P_4$ 的十种自然单顶点扩展,称之为珠宝,并研究在通过禁止这些图的子图作为诱导子图所获得的 $1024$ 个图类上这两种洪水游戏的复杂性。我们的主要贡献是为不包含三个珠宝(bull、gem 和 $P_5$)的图提供了一种自由 Flood-It 的多项式时间算法,覆盖 $128$ 个图类。此外,我们证明两种变体在排除八个珠宝(banner、co-banner、chair、gem、house、kite、$P_5$ 和 $C_5$)的薄蜘蛛图上仍然是 NP-完全的,从而为额外的 $256$ 个类建立了复杂性。结合已知的算法和复杂性结果,我们的工作确定了这两种 Flood-It 变体在 $1024$ 个图类中的 $896$ 个的复杂性。

原文链接: https://arxiv.org/abs/2606.23837

[h] 返回首页