如何高效计数r-均匀超图中的极大团？

基础定义 #

• r-均匀超图：类似普通图，但边被定义为包含r个节点的集合，普通图本质是2-均匀超图。
• 设H为含n个顶点的r-均匀超图。
• 团：顶点集合C，满足|C|=k，且C的所有C(k,r)个r元子集均为H的边。
  • 注意：每个(r-1)元顶点子集都是平凡团。
  • 极大团：若一个团不被任何更大的团包含，则称其为极大团。

核心问题 #

给定含n个顶点的r-均匀超图H，如何高效计数其中的所有极大团（包括平凡极大团）？

当前采用的方法及优化 #

目前使用穷举搜索法，流程如下：

1. 初始阶段：从所有C(n,r-1)个平凡团开始。
2. 迭代检查：对r≤s≤n，逐一检查V(H)的每个s元子集是否为团：
   • 若判定为团，将其加入团集合，并移除所有尚未被移除的、包含于该团的子团（最多C(s,s-1)个）。
3. 表示方式：用位向量表示边和团，第i位为1表示节点i存在于边或团中，也可切换为其他表示方式。

优化方向：将s元子集的检查范围限制为每个顶点度数≥C(s-1,r-1)的集合——这是s-团中顶点的最小可能度数。

两种起始条件 #

需要多次运行上述方法，存在两种起始场景：

• 起始条件1：输入为含n条边的r-均匀超图，对其团结构完全未知。
• 起始条件2：已知含n个顶点的r-均匀超图H的极大团计数结果及完整的极大团集合，通过“翻转”H的一条潜在边得到H'（H'与H仅在某一个r元顶点集合是否为边这一点上不同）。

注：实际场景中，遇到条件2的频次远高于条件1。

示例 #

• 输入：H是含n个顶点的完全r-均匀超图（n≥r），有t种颜色，所有边颜色相同。
• 输出：1 + (t-1)*C(n,r-1)
• 说明：存在一个包含H所有顶点的大极大团；对于其余(t-1)种颜色，每种颜色对应所有平凡极大团。

内容的提问来源于stack exchange，提问作者Dave