Balanced connected partitions of graphs: approximation, parameterization and lower bounds

Phablo F. S. Moura (), Matheus J. Ota () and Yoshiko Wakabayashi ()
Additional contact information
Phablo F. S. Moura: KU Leuven
Matheus J. Ota: University of Waterloo
Yoshiko Wakabayashi: Universidade de São Paulo

Journal of Combinatorial Optimization, 2023, vol. 45, issue 5, No 17, 27 pages

Abstract: Abstract A connected k-partition of a graph is a partition of its vertex set into k classes such that each class induces a connected subgraph. Finding a connected k-partition in which the classes have similar size is a classical problem that has been investigated since late seventies. We consider a more general setting in which the input graph $$G=(V,E)$$ G = ( V , E ) has a nonnegative weight assigned to each vertex, and the aim is to find a connected k-partition in which every class has roughly the same weight. In this case, we may either maximize the weight of a lightest class (max–min BCP $$_k$$ k ) or minimize the weight of a heaviest class (min–max BCP $$_k$$ k ). Both problems are $$\text {\textsc {NP}}$$ NP -hard for any fixed $$k\ge 2$$ k ≥ 2 , and equivalent only when $$k=2$$ k = 2 . In this work, we propose a simple pseudo-polynomial $$\frac{3}{2}$$ 3 2 -approximation algorithm for min–max BCP $$_3$$ 3 , which is an $$\mathcal {O}(|V ||E |)$$ O ( | V | | E | ) time $$\frac{3}{2}$$ 3 2 -approximation for the unweighted version of the problem. We show that, using a scaling technique, this algorithm can be turned into a polynomial-time $$(\frac{3}{2} +{\varepsilon })$$ ( 3 2 + ε ) -approximation for the weighted version of the problem with running-time $$\mathcal {O}(|V |^3 |E |/ {\varepsilon })$$ O ( | V | 3 | E | / ε ) , for any fixed $${\varepsilon }>0$$ ε > 0 . This algorithm is then used to obtain, for min–max BCP $$_k$$ k , $$k\ge 4$$ k ≥ 4 , analogous results with approximation ratio $$(\frac{k}{2}+{\varepsilon })$$ ( k 2 + ε ) . For $$k\in \{4,5\}$$ k ∈ { 4 , 5 } , we are not aware of algorithms with approximation ratios better than those. We also consider fractional bipartitions that lead to a unified approach to design simpler approximations for both min–max and max–min versions. Additionally, we propose a fixed-parameter tractable algorithm based on integer linear programming for the unweighted max–min BCP parameterized by the size of a vertex cover. Assuming the Exponential-Time Hypothesis, we show that there is no subexponential-time algorithm to solve the max–min and min–max versions of the problem.

Keywords: Balanced connected partition; Fractional partition; Approximation algorithms; Fixed parameter tractable; Complexity lower bound; 68Q25; 68W25; 05C85 (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-023-01058-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:45:y:2023:i:5:d:10.1007_s10878-023-01058-x

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-023-01058-x

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().