Approximation and parameterized algorithms to find balanced connected partitions of graphs

• Published in: arXiv.org 2021-08
• Main Authors: Moura, Phablo F S, Ota, Matheus J, Wakabayashi, Yoshiko
• Format: Article
• Language: English
• Subjects: Algorithms; Approximation; Graph theory; Integer programming; Linear programming; Parameterization; Partitions (mathematics); Polynomials; Run time (computers); Weighting functions
• ISSN: 2331-8422

Partitioning a connected graph into \(k\)~vertex-disjoint connected subgraphs of similar (or given) orders is a classical problem that has been intensively investigated since late seventies. Given a connected graph \(G=(V,E)\) and a weight function \(w : V \to \mathbb{Q}_\geq\), a connected \(k\)-partition of \(G\) is a partition of \(V\) such that each class induces a connected subgraph. The balanced connected \(k\)-partition problem consists in finding a connected \(k\)-partition in which every class has roughly the same weight. To model this concept of balance, one may seek connected \(k\)-partitions that either maximize the weight of a lightest class \((\text{max-min BCP}_k)\) or minimize the weight of a heaviest class \((\text{min-max BCP}_k)\). Such problems are equivalent when \(k=2\), but they are different when \(k\geq 3\). In this work, we propose a simple pseudo-polynomial \(\frac{k}{2}\)-approximation algorithm for \(\text{min-max BCP}_k\) which runs in time \(\mathcal{O}(W|V||E|)\), where \(W = \sum_{v \in V} w(v)\). Based on this algorithm and using a scaling technique, we design a (polynomial) \((\frac{k}{2} +\varepsilon)\)-approximation for the same problem with running-time \(\mathcal{O}(|V|^3|E|/\varepsilon)\), for any fixed \(\varepsilon>0\). Additionally, we propose a fixed-parameter tractable algorithm based on integer linear programming for the unweighted \(\text{max-min BCP}_k\) parameterized by the size of a vertex cover.