论文标题
级别化多功能模拟网络和多路切割问题的内核化
Quasipolynomial multicut-mimicking networks and kernelization of multiway cut problems
论文作者
论文摘要
我们显示了一个确切的模仿网络的存在，该网络的$ k^{o（\ log k）} $边缘是在无方面的一组终端上的最低多次数的边缘，其中$ k $是终端的总容量，也是一种计算quasipolyNomial simialial sige ynomial simialial simial homial homial homial homial time time ynomial sime的方法。由于后者的结果，显示了几个问题具有准物质内核，包括边缘多路切割，为任意组设置的组反馈边缘以及通过解决方案和切割请求的数量进行参数的Edge多图。结果结合了内核中基于矩阵的无关边缘方法，以$ s $ -Multiway的切割，并沿稀疏切割的递归分解和递归分解和稀疏。这是自$ s $ -Multiway的固定价值以$ s $的固定价值以来的多道路削减问题的内核的第一个进展（Kratsch和Wahlström，focs 2012）。
We show the existence of an exact mimicking network of $k^{O(\log k)}$ edges for minimum multicuts over a set of terminals in an undirected graph, where $k$ is the total capacity of the terminals, as well as a method for computing a mimicking network of quasipolynomial size in polynomial time. As a consequence of the latter, several problems are shown to have quasipolynomial kernels, including Edge Multiway Cut, Group Feedback Edge Set for an arbitrary group, and Edge Multicut parameterized by the solution and the number of cut requests. The result combines the matroid-based irrelevant edge approach used in the kernel for $s$-Multiway Cut with a recursive decomposition and sparsification of the graph along sparse cuts. This is the first progress on the kernelization of Multiway Cut problems since the kernel for $s$-Multiway Cut for constant value of $s$ (Kratsch and Wahlström, FOCS 2012).
