论文标题
最小$ k $ cut的参数化近似方案
A Parameterized Approximation Scheme for Min $k$-Cut
论文作者
论文摘要
在最小$ k $ cut问题中，输入是一个边缘加权图$ g $和一个整数$ k $，其任务是将顶点设置划分为$ k $非空置集，因此边缘的总重量带有不同零件的端点的总重量。当$ k $是输入的一部分时，问题是NP填充，并且在任何因素不到$ 2 $的任何因素内都难以大致。最近，从参数化近似的角度来看，该问题受到了很大的关注。 Gupta等人〜[SODA 2018]发起了针对Min $ k $ - CUT问题的FPT-AppRoximation的研究，并给出了$ 1.9997 $ -Approximation Algorithm的时间$ 2^{\ Mathcal {o}（k^6）（k^6）} n^n^n^{\ Mathcal {\ Mathcal {o} $} $后来，同一组作者〜[focs 2018]设计了一个$（1 +ε）$ - 近似算法，该算法在时间$ $ $（k/ε）^{\ Mathcal {\ Mathcal {o}（k）} n^{k +\ n^{k +\ mathcal {o \ i}（o i}（1）}（1）} $和$ 1.81 $ -Approximatimation an $ 2^{\ Mathcal {O}（k^2）} n^{\ Mathcal {o}（1）} $。最近，Kawarabayashi和Lin〜 [SODA 2020]给出了$（5/3 +ε）$ - Min $ k $ -cut的近似值，以$ 2^{\ Mathcal {O}（k^2 \ log K）} n^n^{\ Mathcal {\ Mathcal {o}（1）} $。 在本文中，我们给出了一种具有最佳近似保证的参数化近似算法，以及最佳的运行时间依赖性（直至指数时间假设（ETH）和指数中的常数）。特别是，对于每$ε> 0 $，该算法就可以在时间$ $ $（k/ε）^{\ Mathcal {o}（k）} n^{\ Mathcal {O} {O}（O}（1）} $中获得$（1 +ε）$ - 近似解决方案。我们算法的主要成分是：一个简单的稀疏过程，一种用于将图形分解为高度连接部分的新多项式时间算法，以及一种具有运行时间$ s^{\ MATHCAL {o}（O}（O}（k）（k）} n^{\ Mathcal {\ Mathcal {\ Mathcal {o {o）的新的精确算法。在这里，$ s $表示至少$ k $ cut中的边数。后两个具有独立的关注。
In the Min $k$-Cut problem, input is an edge weighted graph $G$ and an integer $k$, and the task is to partition the vertex set into $k$ non-empty sets, such that the total weight of the edges with endpoints in different parts is minimized. When $k$ is part of the input, the problem is NP-complete and hard to approximate within any factor less than $2$. Recently, the problem has received significant attention from the perspective of parameterized approximation. Gupta et al.~[SODA 2018] initiated the study of FPT-approximation for the Min $k$-Cut problem and gave an $1.9997$-approximation algorithm running in time $2^{\mathcal{O}(k^6)}n^{\mathcal{O}(1)}$. Later, the same set of authors~[FOCS 2018] designed an $(1 +ε)$-approximation algorithm that runs in time $(k/ε)^{\mathcal{O}(k)}n^{k+\mathcal{O}(1)}$, and a $1.81$-approximation algorithm running in time $2^{\mathcal{O}(k^2)}n^{\mathcal{O}(1)}$. More, recently, Kawarabayashi and Lin~[SODA 2020] gave a $(5/3 + ε)$-approximation for Min $k$-Cut running in time $2^{\mathcal{O}(k^2 \log k)}n^{\mathcal{O}(1)}$. In this paper we give a parameterized approximation algorithm with best possible approximation guarantee, and best possible running time dependence on said guarantee (up to Exponential Time Hypothesis (ETH) and constants in the exponent). In particular, for every $ε> 0$, the algorithm obtains a $(1 +ε)$-approximate solution in time $(k/ε)^{\mathcal{O}(k)}n^{\mathcal{O}(1)}$. The main ingredients of our algorithm are: a simple sparsification procedure, a new polynomial time algorithm for decomposing a graph into highly connected parts, and a new exact algorithm with running time $s^{\mathcal{O}(k)}n^{\mathcal{O}(1)}$ on unweighted (multi-) graphs. Here, $s$ denotes the number of edges in a minimum $k$-cut. The latter two are of independent interest.
