We present a parameterized dichotomy for the \textsc{$k$-Sparsest Cut} problem in weighted and unweighted versions. In particular, we show that the weighted \textsc{$k$-Sparsest Cut} problem is NP-hard for every $k\geq 3$ even on graphs with bounded vertex cover number. Also, the unweighted \textsc{$k$-Sparsest Cut} problem is W[1]-hard when parameterized by the three combined parameters tree-depth, feedback vertex set number, and $k$. On the positive side, we show that unweighted \textsc{$k$-Sparsest Cut} problem is FPT when parameterized by the vertex cover number and $k$, and when $k$ is fixed, it is FPT with respect to the treewidth. Moreover, we show that the generalized version \textsc{$k$-Small-Set Expansion} problem is FPT when parameterized by $k$ and the maximum degree of the graph, though it is W[1]-hard for each of these parameters separately.
翻译：我们提出了问题 \textsc{$k$-Sparsest Cut} 的参数化二分法，包括加权和非加权版本。特别地，我们证明了加权 \textsc{$k$-Sparsest Cut} 问题对每个 $k \geq 3$ 都是 NP-hard 的，即使在顶点覆盖数有界的图上也是如此。此外，当参数为树的深度、反馈顶点集数量和 $k$ 的组合参数时，非加权 \textsc{$k$-Sparsest Cut} 问题是 W [1]-hard 的。在积极的一面上，我们展示了当参数为顶点覆盖数字和 $k$ 时，未加权 \textsc{$k$-Sparsest Cut} 问题是 FPT 的。当 $k$ 固定时，它相对于树宽是 FPT 的。此外，我们展示了广义版本 \textsc{$k$-Small-Set Expansion} 问题在参数为 $k$ 和图的最大度数时是 FPT 的，虽然它对于每个单独的参数都是 W [1]-hard 的。
相关内容
微信扫码咨询专知VIP会员