DAG with smallest number of vertices

Posted on January 26, 2023
Tags: ,

寒假听到一个问题，家族中有多少对父子多少对爷爷和孙子，问家族中人数最少有几人。

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

1 一个更简单的版本?

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

嗯… |V|=|E|+t|V|=|E|+t, tt是树的个数.
  1. 长度越长的路径显然数量要少于长度短的路径数量
  2. 如果只有一个约束(长度为ll的路径数量是aa), 可以贪心解决

1.1 2/6 点数的upperbound?

arborescence 情况下， 点数的上界是∑ai(li+1)\sum a_i(l_i+1).

(ai(li+1)a_i(l_i+1)的排序与lil_i的排序应该是没什么关系的)

也许能够证明最优解中点数的上界是 max⁡{ai(li+1)}\max \{a_i(l_i+1)\} ?

arborescence 可以看成 intersection of two matroids

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

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

1.2 也许 greedy 可行

把约束按照LiL_i从大到小排序， 对于一个长度是LiL_i的路径数量是aia_i条这样的约束， 构造这样一个有向树: 
O -> O -> ... -> O -> O
      \-> O       \-> O
       |-> O       |-> O
      ...         ...

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

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

换一种描述方法: 假设根的深度是 0. 用一个 pair(Li,Ai)(L_i, A_i)来表示一个路径数量的约束(长度为LiL_i的路径有AiA_i条), 把这些 pair 按照 LiL_i 的降序排序. 最优解的树形图形状像上面画的一样， 深度为L1L_1, 所有深度为pp的顶点都是同一个深度为p−1p-1的顶点的子节点. 深度为L1L_1的节点有A1A_1个， 深度为Li(i≥2)L_i(i\geq 2) 的顶点有 Ai−Ai−1+Li−Li−1+1A_i-A_{i-1}+L_i-L_{i-1}+1 个.

只有一个路径数量约束(长度为LL的路径数量是AA), |V|=L+A|V|=L+A

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

|V|=L1+A1+∑i=2NAi−Ai−1+Li−Li−1=AN+LN \begin{align*} |V|&=L_1+A_1+\sum_{i=2}^N A_i-A_{i-1}+L_i-L_{i-1}\\ &= A_N+L_N \end{align*}

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

2 DAG

不允许重边存在.

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

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

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

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

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

然后考虑一下连接了所有 n(n−1)/2n(n-1)/2 条边的 DAG 如果要保证长度为 L 的路径数量最多(仍然是 (nL+1)\binom{n}{L+1} ), 最多可以删除多少条边？

对于 n=4n=4 的 DAG 和 L=2L=2 , 我们最多可以删掉一个边 (1,4)(1,4), 就是上面的图； 对于 L=3L=3 就可以只保留 (1,2),(2,3),(3,4)(1,2), (2,3), (3,4) 了； L=1L=1 一条边都不能删除.

可以删掉的边数只与 LL 有关， 是 L(L−1)/2L(L-1)/2 (ii 和 jj 不能相邻的条件是 n−(j−i+1)≤L−2n-(j-i+1)\leq L-2)

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