过年的时候听到一个考察小朋友的问题，家族中有多少对父子多少对爷爷和孙子，问家族中人数最少有几人。

把这个问题变成，考虑一个DAG，给出DAG中长度（边的数量）为 的路径的数量 ，求出顶点数量最少的满足条件的DAG

一个更简单的版本?

如果不是一般的 DAG ，而是一个 arborescence ？

嗯… , 是树的个数.

  1. 长度越长的路径显然数量要少于长度短的路径数量
  2. 如果只有一个约束(长度为 的路径数量是 ), 可以贪心解决

2/6 点数的upperbound?

arborescence 情况下, 点数的上界是 .

( 的排序与 的排序应该是没什么关系的)

也许能够证明最优解中点数的上界是 ?

arborescence 可以看成 intersection of two matroids

然而我们关于长度为 的路径的数量的约束却并不是matroid. ground set 是一个 arborescence 森林中的边, 如果长度为 的路径数量小于等于 , 选择的边集就是一个independent set. 这种描述不能满足 exchange property.

(本来还想通过说明即使只有一个路径数量约束也是 intersection of three matroids 来证明即使是arborescence这个问题也是NP-Hard…不过就算成立也不能这样说明.)

也许 greedy 可行

把约束按照 从大到小排序, 对于一个长度是 的路径数量是 条这样的约束, 构造这样一个有向树:

O -> O -> ... -> O -> O
      \-> O       \-> O
       |-> O       |-> O
      ...         ...

在 对应的深度的顶点插入合适数量的儿子.

然后根据构造出的有向树中长度为更小的 的路径的数量并修改 .

换一种描述方法: 假设根的深度是0. 用一个pair 来表示一个路径数量的约束(长度为 的路径有 条), 把这些pair按照 的降序排序. 最优解的树形图形状像上面画的一样, 深度为 , 所有深度为 的顶点都是同一个深度为 的顶点的子节点. 深度为 的节点有 个, 深度为 的顶点有 个.

只有一个路径数量约束(长度为 的路径数量是 ),

观察到对于 个路径约束, 使用的点数总共是

也可以验证这样的构造恰好满足长度为 的路径有 条.

DAG

不允许重边存在.

arborescence 情况下的贪心不再成立了, 比如这样的图:

L2A4V4

有向树的情况下是4个点是形成不了4条长度为2的路径的.

个点的DAG形成的长度为 的路径数量?

就是一个把能连接的边全部连接上的DAG吧。

路径数量就是组合数, 表示 个点的DAG形成的长度为 的路径数量, 看起来可能要找递推关系用生成函数算了, 但是实际上 相当于 在 当中包含 个元素的子集的个数, 给这个DAG拓扑排序, 所有可能的路径都是序列 的所有子序列, 数量也就是包含 个元素的子集个数. generatingfunctionology 1.5 是用生成函数算组合数的例子.

然后考虑一下连接了所有 条边的DAG如果要保证长度为L的路径数量最多(仍然是 ), 最多可以删除多少条边?

对于 的DAG和 , 我们最多可以删掉一个边 , 就是上面的图; 对于 就可以只保留 了; 一条边都不能删除.

可以删掉的边数只与 有关, 是 ( 和 不能相邻的条件是 )

目前还没有想到接下来该怎么办…