Fixed-Parameter Algorithms for Cardinality-Constrained Graph Partitioning Problems on Sparse Graphs

For an undirected and edge-weighted graph \(G=(V, E)\) and a vertex subset \(S\subseteq V\) , we define a function \(\varphi _{G}(S) := (1-\alpha )\cdot w(S) + \alpha \cdot w(S, V\setminus S)\) , where \(\alpha \in [0, 1]\) is a real number, w(S) is the sum of weights of edges having two endpoints in S, and \(w(S, V\setminus S)\) is the sum of weights of edges having one endpoint in S and the other in \(V\setminus S\) . Then, given a graph \(G=(V, E)\) and a positive integer k, Max (Min) \(\alpha \) -Fixed Cardinality Graph Partitioning (Max (Min) \(\alpha \) -FCGP) is the problem to find a vertex subset \(S\subseteq V\) of size k that maximizes (minimizes) \(\varphi _{G}(S)\) . In this paper, we first show that Max \(\alpha \) -FCGP with \(\alpha \in [1/3,1]\) and Min \(\alpha \) -FCGP with \(\alpha \in [0,1/3]\) can be solved in time \(2^{o(kd+k)}(e+ed)^k n^{O(1)}\) where k is the solution size, d is the degeneracy of an input graph, and e is Napier’s constant.Then we consider Max (Min) Connected \(\alpha \) -FCGP, which additionally requires the connectivity of a solution. For Max (Min) Connected \(\alpha \) -FCGP, we give an \((e (\varDelta -1))^{k-1}n^{O(1)}\) -time algorithm on general graphs and a \(2^{O(\sqrt{k} \log ^2 k)}n^{O(1)}\) -time randomized algorithm on apex-minor-free graphs. Moreover, for Max \(\alpha \) -FCGP with \(\alpha \in [1/3,1]\) and Min \(\alpha \) -FCGP with \(\alpha \in [0,1/3]\) , we propose an \((1+d)^k 2^{o(kd)+O(k)} n^{O(1)}\) -time algorithm. Finally, we show that they admit FPT-ASs when edge weights are constant.