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⊆V, we define a function φ_G(formula presented), where (formula presented) is a real number, w(S) is the sum of weights of edges having two endpoints in S, and w(S,V\S) is the sum of weights of edges having one endpoint in S and the other in V\S. Then, given a graph G=(V,E) and a positive integer k, Max (Min) α-Fixed Cardinality Graph Partitioning (Max (Min) α-FCGP) is the problem to find a vertex subset (formula presented) of size k that maximizes (minimizes) φ_G(S). In this paper, we first show that Max α-FCGP with (formula presented) and Minα-FCGP with (formula presented) can be solved in time (formula presented)-time algorithm on general graphs and a (formula presented)-time randomized algorithm on apex-minor-free graphs. Moreover, for Max α-FCGP with (formula presented) and Min (formula presented), we propose an (1+d)^k2^o(kd)+O(k)n^O(1)-time algorithm. Finally, we show that they admit FPT-ASs when edge weights are constant.