基于toggle测试函数从拓扑序恢复原始DAG的多项式时间解法咨询

是否存在多项式时间解法？ #

存在。利用已知的拓扑序列，我们可以通过多项式次数的toggle调用逐步确定每个节点的直接父节点，具体步骤如下：

1. 识别根节点 #

初始所有节点状态为0，对每个节点执行toggle操作：

• 成功执行的节点即为根节点（无任何直接/间接父节点，满足“所有父节点为1”的空真条件）。
• 记录所有根节点，后续处理中它们的依赖闭包仅包含自身。

2. 按拓扑序处理非根节点 #

设拓扑序列为v₁, v₂, ..., vₙ，对每个非根节点vᵢ（i > 1）执行以下操作：

步骤2.1：确定vᵢ的依赖闭包（所有直接/间接父节点）

依赖闭包Sᵢ是所有满足“若该节点为0，则toggle(vᵢ)必然失败”的前驱节点（拓扑序中位于vᵢ之前的节点）。测试方法：

• 每次测试前重置所有节点状态为0。
• 对每个前驱节点vⱼ（j < i）：
  1. 按拓扑序将除vⱼ外的所有前驱节点逐一toggle为1（因拓扑序保证前驱的父节点已被处理，这些toggle操作都会成功）。
  2. 尝试toggle(vᵢ)：
     • 若失败，说明vⱼ是vᵢ的父节点（直接/间接），将vⱼ加入Sᵢ。
     • 若成功，说明vⱼ与vᵢ无依赖关系，排除出Sᵢ。

步骤2.2：从依赖闭包中提取直接父节点

对于Sᵢ中的每个节点vⱼ，检查是否存在其他节点vₖ ∈ Sᵢ（k ≠ j）使得vⱼ属于vₖ的依赖闭包Sₖ：

• 若不存在这样的vₖ，则vⱼ是vᵢ的直接父节点（无中间节点传递依赖）。
• 若存在，则vⱼ是vᵢ的间接父节点，跳过。

时间复杂度分析 #

• 每个节点vᵢ需测试O(i)个前驱节点，每次测试需O(i)次toggle操作。
• 总时间复杂度为O(n³)，属于多项式时间范畴（n为节点总数）。

问题的相关名称 #

该问题属于黑箱DAG结构识别的范畴，也可归类为：

• 依赖关系挖掘：通过查询操作推断节点间的依赖链路。
• 基于查询的DAG重构：利用成员查询（toggle函数本质是一种依赖满足性查询）还原DAG结构。
• 在因果推断领域，类似问题被称为因果结构学习（但后者通常处理概率性依赖，而本题是确定性依赖）。

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