论文标题
在有向图中线性跨度的稀疏下限
Sparsification Lower Bound for Linear Spanners in Directed Graphs
论文作者
论文摘要
对于$α\ ge 1 $，$β\ ge 0 $，以及图$ g $，如果$ \ dist（u，v，v，h）\ leα\ cdot \ cdot \ cdot \ dist（u，v，v，g） +β$ for noper noper和$ u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u u $这些类型的跨度，称为\ emph {线性跨度}，概括\ emph {addive spanners}和\ emph {乘法跨度}。最近，Fomin，Golovach，Lochet，Misra，Saurabh和Sharma启动了针对有向图的添加剂和乘法跨度的研究（IPEC $ 2020 $）。在本文中，我们继续进行这一研究，并证明\ textsc {定向线性跨度}通过顶点$ n $的数量进行参数化，除非$ \ galo（n^{2 -ε}）$的多项式压缩，除非$ \ np \ np \ np \ subseteq \ subseteq \ conp conp/poly $ conp/poly $。我们表明，\ textsc {有向添加剂启动器}和\ textsc {有向的乘法启动器}问题的相似结果。即使输入是有向的无环形图，$α，β$也是\ emph {any}可计算函数，即使输入是有向的无环形图，也是如此。
For $α\ge 1$, $β\ge 0$, and a graph $G$, a spanning subgraph $H$ of $G$ is said to be an $(α, β)$-spanner if $\dist(u, v, H) \le α\cdot \dist(u, v, G) + β$ holds for any pair of vertices $u$ and $v$. These type of spanners, called \emph{linear spanners}, generalizes \emph{additive spanners} and \emph{multiplicative spanners}. Recently, Fomin, Golovach, Lochet, Misra, Saurabh, and Sharma initiated the study of additive and multiplicative spanners for directed graphs (IPEC $2020$). In this article, we continue this line of research and prove that \textsc{Directed Linear Spanner} parameterized by the number of vertices $n$ admits no polynomial compression of size $\calO(n^{2 - ε})$ for any $ε> 0$ unless $\NP \subseteq \coNP/poly$. We show that similar results hold for \textsc{Directed Additive Spanner} and \textsc{Directed Multiplicative Spanner} problems. This sparsification lower bound holds even when the input is a directed acyclic graph and $α, β$ are \emph{any} computable functions of the distance being approximated.
