IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v45y2023i5d10.1007_s10878-023-01058-x.html
   My bibliography  Save this article

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

Author

Listed:
  • Phablo F. S. Moura

    (KU Leuven)

  • Matheus J. Ota

    (University of Waterloo)

  • Yoshiko Wakabayashi

    (Universidade de São Paulo)

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.

Suggested Citation

  • Phablo F. S. Moura & Matheus J. Ota & Yoshiko Wakabayashi, 2023. "Balanced connected partitions of graphs: approximation, parameterization and lower bounds," Journal of Combinatorial Optimization, Springer, vol. 45(5), pages 1-27, July.
  • Handle: RePEc:spr:jcomop:v:45:y:2023:i:5:d:10.1007_s10878-023-01058-x
    DOI: 10.1007/s10878-023-01058-x
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10878-023-01058-x
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.

    File URL: https://libkey.io/10.1007/s10878-023-01058-x?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Ravi Kannan, 1987. "Minkowski's Convex Body Theorem and Integer Programming," Mathematics of Operations Research, INFORMS, vol. 12(3), pages 415-440, August.
    2. H. W. Lenstra, 1983. "Integer Programming with a Fixed Number of Variables," Mathematics of Operations Research, INFORMS, vol. 8(4), pages 538-548, November.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Li, Weidong & Ou, Jinwen, 2024. "Machine scheduling with restricted rejection: An Application to task offloading in cloud–edge collaborative computing," European Journal of Operational Research, Elsevier, vol. 314(3), pages 912-919.
    2. Niclas Boehmer & Edith Elkind, 2020. "Stable Roommate Problem with Diversity Preferences," Papers 2004.14640, arXiv.org.
    3. Klaus Jansen & Kim-Manuel Klein & José Verschae, 2020. "Closing the Gap for Makespan Scheduling via Sparsification Techniques," Mathematics of Operations Research, INFORMS, vol. 45(4), pages 1371-1392, November.
    4. Klaus Jansen & Roberto Solis-Oba, 2011. "A Polynomial Time OPT + 1 Algorithm for the Cutting Stock Problem with a Constant Number of Object Lengths," Mathematics of Operations Research, INFORMS, vol. 36(4), pages 743-753, November.
    5. Matthias Bentert & Robert Bredereck & Péter Györgyi & Andrzej Kaczmarczyk & Rolf Niedermeier, 2023. "A multivariate complexity analysis of the material consumption scheduling problem," Journal of Scheduling, Springer, vol. 26(4), pages 369-382, August.
    6. William Cook & Thomas Rutherford & Herbert E. Scarf & David F. Shallcross, 1991. "An Implementation of the Generalized Basis Reduction Algorithm for Integer Programming," Cowles Foundation Discussion Papers 990, Cowles Foundation for Research in Economics, Yale University.
    7. D. V. Gribanov & D. S. Malyshev & P. M. Pardalos & S. I. Veselov, 2018. "FPT-algorithms for some problems related to integer programming," Journal of Combinatorial Optimization, Springer, vol. 35(4), pages 1128-1146, May.
    8. A. Yu. Chirkov & D. V. Gribanov & D. S. Malyshev & P. M. Pardalos & S. I. Veselov & N. Yu. Zolotykh, 2019. "On the complexity of quasiconvex integer minimization problem," Journal of Global Optimization, Springer, vol. 73(4), pages 761-788, April.
    9. K. Aardal & R. E. Bixby & C. A. J. Hurkens & A. K. Lenstra & J. W. Smeltink, 2000. "Market Split and Basis Reduction: Towards a Solution of the Cornuéjols-Dawande Instances," INFORMS Journal on Computing, INFORMS, vol. 12(3), pages 192-202, August.
    10. Alberto Del Pia & Robert Hildebrand & Robert Weismantel & Kevin Zemmer, 2016. "Minimizing Cubic and Homogeneous Polynomials over Integers in the Plane," Mathematics of Operations Research, INFORMS, vol. 41(2), pages 511-530, May.
    11. Friedrich Eisenbrand & Gennady Shmonin, 2008. "Parametric Integer Programming in Fixed Dimension," Mathematics of Operations Research, INFORMS, vol. 33(4), pages 839-850, November.
    12. Masing, Berenike & Lindner, Niels & Borndörfer, Ralf, 2022. "The price of symmetric line plans in the Parametric City," Transportation Research Part B: Methodological, Elsevier, vol. 166(C), pages 419-443.
    13. Chen, Lin & Ye, Deshi & Zhang, Guochuan, 2018. "Parallel machine scheduling with speed-up resources," European Journal of Operational Research, Elsevier, vol. 268(1), pages 101-112.
    14. Danny Nguyen & Igor Pak, 2020. "The Computational Complexity of Integer Programming with Alternations," Mathematics of Operations Research, INFORMS, vol. 45(1), pages 191-204, February.
    15. Sascha Kurz & Nikolas Tautenhahn, 2013. "On Dedekind’s problem for complete simple games," International Journal of Game Theory, Springer;Game Theory Society, vol. 42(2), pages 411-437, May.
    16. Elizabeth Baldwin & Paul Klemperer, 2019. "Understanding Preferences: “Demand Types”, and the Existence of Equilibrium With Indivisibilities," Econometrica, Econometric Society, vol. 87(3), pages 867-932, May.
    17. Herbert E. Scarf & David F. Shallcross, 2008. "The Frobenius Problem and Maximal Lattice Free Bodies," Palgrave Macmillan Books, in: Zaifu Yang (ed.), Herbert Scarf’s Contributions to Economics, Game Theory and Operations Research, chapter 7, pages 149-153, Palgrave Macmillan.
    18. Elhedhli, Samir & Naoum-Sawaya, Joe, 2015. "Improved branching disjunctions for branch-and-bound: An analytic center approach," European Journal of Operational Research, Elsevier, vol. 247(1), pages 37-45.
    19. Mauro Dell’Amico & Simone Falavigna & Manuel Iori, 2015. "Optimization of a Real-World Auto-Carrier Transportation Problem," Transportation Science, INFORMS, vol. 49(2), pages 402-419, May.
    20. Karen Aardal & Cor A. J. Hurkens & Arjen K. Lenstra, 2000. "Solving a System of Linear Diophantine Equations with Lower and Upper Bounds on the Variables," Mathematics of Operations Research, INFORMS, vol. 25(3), pages 427-442, August.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:jcomop:v:45:y:2023:i:5:d:10.1007_s10878-023-01058-x. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.