Fixed parameter approximation scheme for min-max \(k\)-cut (Q5925652)

The main aim of this paper is to consider graph partitioning under the minmax objective. In general, graph partitioning problems are important for their intrinsic theoretical value and also applications in clustering. Let \(G=(V, E)\) be a graph with non-negative integral edge weights \(w:E\rightarrow \mathbb{Z}_{+}\) along with an integer \(k\geq 2\). Our aim is to partition the vertices of \(G\) into \(k\) non-empty parts \(V_1, V_2, \ldots, V_k\) so as to minimize \(\max_{i=1}^k w(\delta(V_i))\), where \(\delta(V_i)\) denotes the set of edges which have exactly one end-vertex in \(V_i\) and \(w(\delta(V_i)):=\sum_{e\in \delta(V_i)} w(e)\) is the total weight of the edges in \(\delta(V_i)\). This problem is called \textsc{Minmax} \(k\)-\textsc{cut}. Historically, using minmax objective for optimization problems has a large literature in approximation algorithms. In particular, in the context of graph cuts and partitioning, recent works have proposed and studied alternative minmax objectives that are different from \textsc{Minmax} \(k\)-\textsc{cut}, see [\textit{S. Ahmadi} et al., Lect. Notes Comput. Sci. 11480, 13--26 (2019; Zbl 1436.90114)] and [\textit{M. Charikar} et al., ibid. 10328, 136--147 (2017; Zbl 1418.90218)]. Moreover, the complexity of \textsc{Minmax} \(k\)-\textsc{cut} was raised as an open problem by \textit{E. L. Lawler} [Networks 3, 275--285 (1973; Zbl 0262.05126)]. The important results in this paper are listed as follows: Theorem 1. \textsc{Minmax} \(k\)-\textsc{cut} is strongly NP-hard and \(W[1]\)-hard when parameterized by \(k\). Theorem 2. There exists a randomized algorithm that takes as input a weighted instance of \textsc{Minmax} \(k\)-\textsc{cut}, namely an \(n\)-vertex simple graph \(G=(V, E)\) with edge weights \(w : E \rightarrow \mathbb{Z}_{+}\) and an integer \(k\geq 2\), along with an \(\epsilon \in (0,1)\), and runs in time \((k/\epsilon)^{O(k^2)}n^{O(1)}\log^{2}(\sum_{e\in E}w(e))\) to return a partition \(\mathcal{P}\) of the vertices of \(G\) such that cost\(_{G_w}(\mathcal{P})\leq (1+\epsilon)OPT(G_w,k)\) with high probability. Theorem 3. There exists an algorithm that takes as input an unweighted instance \(G=(V,E)\) of \textsc{Minmax} \(k\)-\textsc{cut}, namely an \(n\)-vertex \(m\)-edge graph \(G=(V,E)\) and an integer \(k\geq 2\), along with an integer \(\lambda\) and runs in time \((k\lambda)^{O(k^2)}n^{O(1)} +O(km)\) to determine if there exists a \(k\)-partition \((V_1, \ldots, V_k)\) of \(V\) such that cost\(_G(V_1, \ldots, V_k)\leq \lambda\) and if so, returns an optimum partition for \textsc{Minmax} \(k\)-\textsc{cut} on \(G\). Theorem 4. There exists an algorithm that takes as input an \(n\)-vertex \(m\)-edge unweighted connected graph \(G = (V, E)\) and an integer \(k\geq 2\), along with an integer \(\lambda\), and runs in time \((k\lambda)^{O(k^2)}n^{O(1)}+O(m)\) to determine if there exists a \(k\)-partition \((V_1, \ldots, V_k)\) of \(V\) such that cost\(_G(V_1,\ldots, V_k)\leq \lambda\) and if so, returns an optimum partition for \textsc{Minmax} \(k\)-\textsc{cut} on \(G\). Furthermore, the algorithmic technique presented in this paper builds on the technique of \textit{D. Lokshtanov} et al. [``A parameterized approximation scheme for Min \(k\)-cut'', in: Proceedings of the 61st IEEE annual Symposium on Foundations of Computer Science, FOCS'20. Los Alamitos, CA: IEEE Computer Society. 798--809 (2020; \url{doi:10.1137/20M1383197})] who showed a similar result for \textsc{Minsum \(k\)-cut}, while the algorithmic techniques in the present paper are more general and can be used to obtain parameterized approximation schemes for minimizing \(\ell_p\)-norm measures of \(k\)-partitioning for every \(p\geq 1\). Finally, the authors conclude this paper with a few open questions in Section 7.