论文标题
准两部分图的最佳顶点切割稀疏
Optimal Vertex-Cut Sparsification of Quasi-Bipartite Graphs
论文作者
论文摘要
在顶点切割稀疏中，给定图形$ g =（v，e）$，带有终端集$ t \ subseteq v $，我们希望构建图形$ g'=（v'，e'）$，带有$ t \ subseteq v'$，以便每两集端子$ a，b f \ b f \ subseteq t $ $ g $ g'$ g'（$ g's $ g'与$ g $相同。在最基本的环境中，$ g $是未加权的和未方向的，我们希望通过$ k = | t | $的函数绑定$ g'$的大小。 Kratsch和Wahlström[JACM 2020]证明，每个图$ g $（可能是指导），承认带有$ o（k^3）$顶点的顶点切换的sparsifier $ g'$，实际上可以在随机的多项式时间内构造。 我们研究（可能是指向）的图形$ g $，即$ t $ g $，即，每个边缘在$ t $中至少具有一个端点，并证明他们承认具有$ o（k^2）$边缘和顶点的顶点切换器，实际上可以在确定性的多项式时间内构造。实际上，该界限自然地延伸到所有图形，并带有一个小型分离器，成为有界大小的集合。最后，从理论上讲，我们证明了信息几乎匹配的下限，即$ \tildeΩ（k^2）$ edges sparsify parsify quasi-partite无向图。
In vertex-cut sparsification, given a graph $G=(V,E)$ with a terminal set $T\subseteq V$, we wish to construct a graph $G'=(V',E')$ with $T\subseteq V'$, such that for every two sets of terminals $A,B\subseteq T$, the size of a minimum $(A,B)$-vertex-cut in $G'$ is the same as in $G$. In the most basic setting, $G$ is unweighted and undirected, and we wish to bound the size of $G'$ by a function of $k=|T|$. Kratsch and Wahlström [JACM 2020] proved that every graph $G$ (possibly directed), admits a vertex-cut sparsifier $G'$ with $O(k^3)$ vertices, which can in fact be constructed in randomized polynomial time. We study (possibly directed) graphs $G$ that are quasi-bipartite, i.e., every edge has at least one endpoint in $T$, and prove that they admit a vertex-cut sparsifier with $O(k^2)$ edges and vertices, which can in fact be constructed in deterministic polynomial time. In fact, this bound naturally extends to all graphs with a small separator into bounded-size sets. Finally, we prove information-theoretically a nearly-matching lower bound, i.e., that $\tildeΩ(k^2)$ edges are required to sparsify quasi-bipartite undirected graphs.
