本文探讨有向图中“全前驱可达”条件下的最小生成器（minimum generator）问题——即寻找最小节点集s，使得图中每个节点要么属于s，要么其所有直接前驱均能从s出发按该规则递归可达；该问题是np难的，等价于最小反馈顶点集问题。
本文探讨有向图中“全前驱可达”条件下的最小生成器（minimum generator）问题——即寻找最小节点集s，使得图中每个节点要么属于s，要么其所有直接前驱均能从s出发按该规则递归可达；该问题是np难的，等价于最小反馈顶点集问题。
在标准图可达性中，只要存在一条有向路径即可判定可达；但本问题引入了更强的约束：一个节点仅当其所有直接前驱（in-neighbors）均已可达时，自身才被视为可达。这一规则本质上模拟了“逻辑与门”的依赖关系——例如在电路仿真、工作流执行或编译器数据流分析中，某操作只有在其全部输入就绪后才能触发。
形式化定义如下：给定有向图 $ G = (V, E) $，集合 $ S \subseteq V $ 是一个生成器（generator），当且仅当对任意节点 $ v \in V $，满足：
- $ v \in S $，或
- 对 $ v $ 的每个前驱 $ u $（即 $ (u,v) \in E $），$ u $ 本身可从 $ S $ 可达（按相同规则递归定义）。
目标是求最小基数的生成器 $ S^ $，即 $ |S^| = \min{ |S| : S \text{ 是 } G \text{ 的生成器} } $。
值得注意的是，该问题不存在多项式时间精确算法（除非 P = NP）。其NP难性可通过归约自经典的最小反馈顶点集（Minimum Feedback Vertex Set, FVS）问题严格证明：
归约构造：对任一有向图 $ G $，构造新图 $ H $：添加一个超级源点 $ v{\text{new}} $，并添加边 $ (v{\text{new}}, u) $ 到 $ G $ 中每个节点 $ u $。
若 $ SH $ 是 $ H $ 的最小生成器，则必有 $ v{\text{new}} \in S_H $（因其无前驱，无法被其他节点“解锁”）；进一步可证 $ SH \setminus {v{\text{new}}} $ 构成 $ G $ 的一个反馈顶点集——即移除该集合后 $ G $ 无环。反之，任一包含 $ v_{\text{new}} $ 与 $ G $ 的FVS的集合，也构成 $ H $ 的合法生成器。
因此，求解最小生成器可直接求解最小FVS，而后者已被证明是NP难的。
实践启示与近似策略：
- 对小规模图（如 $ |V| \leq 25 $），可建模为整数线性规划（ILP）：为每个节点 $ v $ 引入二进制变量 $ x_v \in {0,1} $ 表示是否选入生成器；添加约束：
$$ \forall v \in V,\quad xv + \sum{u \in \text{Pred}(v)} xu \geq 1 $$
其中 $ \text{Pred}(v) = { u \mid (u,v) \in E } $。目标为最小化 $ \sum{v \in V} x_v $。 - 对大规模图，可采用贪心启发式：优先选择入度为0的节点（必须入选），再迭代收缩已覆盖子图，或基于循环结构识别关键割点；也可调用现成的FVS求解器（如使用SAT编码或商用求解器Gurobi/CPLEX）间接求解。
- 特别注意：若图是有向无环图（DAG），则最小生成器即为所有入度为0的节点集合——此时问题退化为线性时间可解。
综上，该问题虽本质困难，但其结构与反馈环紧密耦合，理解其与FVS的等价性，是设计高效近似算法或合理建模的关键前提。
