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)\} ?

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 情况下的贪心不再成立了， 比如这样的图:

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

2026-09-23 chatgpt 6 pro 证明了这问题 strongly NP-hard https://chatgpt.com/share/6ab39688-b594-83ea-97fb-feb6a4eda32f