arXiv:2504.16837v1 宣告类型：交叉 摘要：在时间图中，边集会根据每条边关联的时间标签动态变化，每个时间标签表明该边在哪些时间步骤可用。如果存在一条路径连接两个顶点，并且路径上的边按照标签的增加顺序被遍历，那么这两个顶点是连接的。我们研究了在给定的最大允许时间$a$内确保所有顶点对都能连接，并且整体标签数量最小的边的可用时间调度问题。这个问题被称为“最小年龄标签化”(Minimum Aged Labeling, MAL)，在物流、分配调度和社会网络中的信息传播等领域有许多应用，明智地选择时间标签可以显著降低基础设施成本、燃料消耗或温室气体排放。 之前已证明，在无向图中该问题NP完全，在有向图中为\APX-hard。本文我们在多个方面扩展了对MAL的复杂性和近似性的了解。首先，我们证明了当$a \geq 2$时，该问题不能在$O(\log n)$因子内近似，除非$\text{P} = \text{NP}$；当$a \geq 3$时，不能在$2^{\log^{1-\epsilon} n}$因子内近似，除非$\text{NP} \subseteq \text{DTIME}(2^{\text{polylog}(n)})$，其中$n$为图中的顶点数。然后我们给出了一组近似算法，在某些条件下几乎匹配这些下界。特别地，我们显示了近似性取决于$a$与输入图直径之间的关系。 我们进一步建立了与静态图上的基础优化问题“直径约束支配子图”(Diameter Constrained Spanning Subgraph, DCSS) 的关联，并证明我们的复杂性结果同样适用于DCSS。